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

Максимальное паросочетание

Максимальное паросочетание

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

Граф (V, E) называется двудольным, если множество его вершин V можно разбить на два подмножества A и B такие, что любое ребро из E соединяет вершину из A с вершиной из B.

Паросочетанием P называется любое подмножество E такое, что никакие два ребра из него не имеют общей вершины.

Максимальное паросочетание - это паросочетание, число рёбер в котором максимально.

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

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

В первой строке заданы три числа n, m и k (1n, m100, 1k10000), где n - число вершин во множестве A, m - число вершин в B, а k - количество рёбер в графе. Каждая из следующих k строк содержит по два числа u[i] и v[i], означающих, что вершина u[i] множества A соединена с ребром v[i] множества B. Вершины во множествах A и B нумеруются по отдельности, начиная с единицы. Все входные числа целые.

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

В первой строке выведите количество l рёбер в максимальном паросочетании. Далее выведите l строк, по два числа в каждой. Числа a[j] и b[j], стоящие в j-ой из этих строк, означают, что паросочетание взято между вершиной a[j] множества A и вершиной b[j] множества B. Взятые рёбра должны образовывать максимальное паросочетание.

prb1989.gif

Пример

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