eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Паросочетание

Паросочетание

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

Дан двудольный невзвешенный граф. Найти максимальное паросочетание.

Входные данные

В первой строке находятся три целых числа n, m и k (1n, m200, 1kn × m) - количество чисел в первой и второй долях, а также число ребер соответственно. Далее следуют k строк, в каждой из которых два числа a[i] и b[i], что означает ребро между вершиной с номером a[i] первой доли и вершиной с номером b[i] второй доли. Вершины в обеих долях нумеруются с единицы.

Выходные данные

В первой строке выведите одно число q - максимальное число ребер в паросочетании. Во второй строке выведите q чисел - номера ребер, принадлежащих максимальному паросочетанию. Ребра нумеруются начиная с единицы в порядке появления на входе.

Пример

Входные данные #1
3 3 5
1 1
1 3
2 1
2 2
3 2
Выходные данные #1
3
2 3 5