Loading [MathJax]/jax/output/CommonHTML/jax.js

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

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

Условие

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

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

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

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

В первой строке записаны два целых числа n и m (1n,m250)  — число вершин в 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.127s 0.011s 13