Задачи
Паросочетание
Паросочетание
Дан двудольный невзвешенный граф. Найти максимальное паросочетание.
Входные данные
В первой строке находятся три целых числа n, m и k (1 ≤ n, m ≤ 200, 1 ≤ k ≤ n × m) - количество чисел в первой и второй долях, а также число ребер соответственно. Далее следуют k строк, в каждой из которых два числа ai
и bi
, что означает ребро между вершиной с номером ai
первой доли и вершиной с номером bi
второй доли. Вершины в обеих долях нумеруются с единицы.
Выходные данные
В первой строке выведите одно число q - максимальное число ребер в паросочетании. Во второй строке выведите q чисел - номера ребер, принадлежащих максимальному паросочетанию. Ребра нумеруются начиная с единицы в порядке появления на входе.
Входные данные #1
3 3 5 1 1 1 3 2 1 2 2 3 2
Выходные данные #1
3 2 3 5