Дан двудольный невзвешенный граф. Найти максимальное паросочетание.
В первой строке находятся три целых числа n, m и k (1 ≤ n, m ≤ 200, 1 ≤ k ≤ n × m) - количество чисел в первой и второй долях, а также число ребер соответственно. Далее следуют k строк, в каждой из которых два числа a[i]
и b[i]
, что означает ребро между вершиной с номером a[i]
первой доли и вершиной с номером b[i]
второй доли. Вершины в обеих долях нумеруются с единицы.
В первой строке выведите одно число q - максимальное число ребер в паросочетании. Во второй строке выведите q чисел - номера ребер, принадлежащих максимальному паросочетанию. Ребра нумеруются начиная с единицы в порядке появления на входе.