Максимальное паросочетание
Максимальное паросочетание
Граф (V, E) называется двудольным, если множество его вершин V можно разбить на два подмножества A и B такие, что любое ребро из E соединяет вершину из A с вершиной из B.
Паросочетанием P называется любое подмножество E такое, что никакие два ребра из него не имеют общей вершины.
Максимальное паросочетание - это паросочетание, число рёбер в котором максимально.
Найдите максимальное паросочетание в заданном двудольном графе.
Входные данные
В первой строке заданы три числа n, m и k (1 ≤ n, m ≤ 100, 1 ≤ k ≤ 10000), где 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. Взятые рёбра должны образовывать максимальное паросочетание.
Пример
2 3 4 1 1 1 2 2 2 2 3
2 1 1 2 3