| Входной файл: | input.txt | Ограничение времени: | 2 сек | |
| Выходной файл: | output.txt | Ограничение памяти: | 256 Мб |
Напишите программу для нахождения максимального двудольного паросочетания.
Входной файл содержит целые числа p, q, m — мощности левой правой доли, а также количество рёбер соответственно.
Далее содержится описание m ребер в виде списка пар целых чисел (ui, vi). Наличие пары (ui, vi) означает ребро между ui-ой вершиной левой доли и vi-ой вершиной правой доли.
Гарантируется, кратных рёбер в графе нет.
Выходной файл должен содержать мощность максимального паросочетания с последующим перечислением рёбер из него в том же формате, что и во входном файле. Если решений несколько, выведите любое.
1 ≤ p, q ≤ 105
1 ≤ m ≤ 2 * 105
1 ≤ ui ≤ p
1 ≤ vi ≤ q
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|