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

Описание

Граф называется двудольным, если его множество вершин V можно разбить на два непересекающихся множества вершин A и B, так чтобы концы любого ребра в этом графе находились в разных множествах. Паросочетанием в графе называется подмножество S множества ребер E этого графа, не имеющих общих вершин (для любых ребер e1 = (u1, v1) и e2 = (u2, v2), лежащих в S, выполнено u1 != u2, u1 != v2, v1 != u2 и v1 != v2). Ваша задача – найти максимальное паросочетание в заданном двудольном графе.

Максимальным называется паросочетание, состоящее из максимального количества ребер.

Формат входных данных

Первая строка входного файла содержит два целых числа N и M (1 <= N,M <= 250) - количество вершин во множествах A и B соответственно. Следующие N строк содержат описания ребер графа. В (i + 1)-й строке содержится список вершин множества B, соединенных с i-й вершиной множества A. Список оканчивается числом 0. Нумерация вершин в множествах A и B независимая (вершины нумеруются c 1).

Формат выходных данных

Первая строка выходного файла должна содержать одно целое число L – количество ребер в максимальном паросочетании. Каждая из следующих L строк должна содержать описание одного ребра паросочетания – два целых числа ui и vi (номер вершины в множестве A и номер вершины в множестве B).