eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Time limit 1 second
Memory limit 122 MiB

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

Input data

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

Output data

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

Examples

Input example #1
3 3 5
1 1
1 3
2 1
2 2
3 2
Output example #1
3
2 3 5