Задача B. Паросочетание

Автор:std.alg   Ограничение времени:2 сек
Входной файл:pairs.in   Ограничение памяти:256 Мб
Выходной файл:pairs.out  

Условие

Двудольным графом называется граф (V,E), E ⊂ V × V такой, что его множество вершин V можно разбить на два подмножества A и B, для которых ∀ (e1,e2) ∈ E e1 ∈ A, e2 ∈ B и A, B ⊂ E, A ∩ B = varnothing.

Паросочетанием в двудольном графе называется любой его набор несмежных ребер, то есть такой набор S ⊂ E, что для любых двух ребер e1 = (u1, v1), e2 = (u2, v2) из S выполнено u1 ≠ u2 и v1 ≠ v2.

Ваша задача — найти максимальное паросочтание в двудольном графе, то есть паросочетание с максимально возможным числом ребер.

Формат входного файла

В первой строке записаны два целых числа n и m (1≤ n, m ≤ 250)  — число вершин в A и число вершин в B.

Далее следуют n строк с описаниями ребер. i-я вершина из A описана в i + 1-й строке файла. Каждая из этих строк содержит номера вершин из B, соединенных с i-й вершиной A. Вершины в A и B нумеруются независимо (с единицы). Список завершается числом 0.

Формат выходного файла

Первая строка выходного файла должна содержать одно целое число l — количество ребер в максимальном паросочетании. Далее должны следовать l строк, в каждой из которых должны быть два целых числа uj и vj — концы ребер паросочетания в A и B, соотвественно.

Ограничения

Примеры тестов

Входной файл (pairs.in) Выходной файл (pairs.out)
1
2 2
1 2 0
2 0
2
1 1
2 2

0.065s 0.009s 13