Автор: | 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=∅.
Паросочетанием в двудольном графе называется любой его набор несмежных ребер, то есть такой набор 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 |
|
|