Максимальное паросочетание

Граф $G=(V,E)$ называется двудольным, если множество его вершин $V$ можно разбить на два подмножества $A$ и $B$ так, что любое ребро из $E$ соединяет вершину из $A$ с вершиной из $B$.

Паросочетанием $P$ называется любое подмножество $E$, такое что никакие два ребра из этого множетва не имеют общих вершин.

Максимальное паросочетание — это паросочетание, содержащее максимальное количество рёбер.

Найдите максимальное паросочетание в заданном двудольном графе.

Входные данные

В первой строке заданы три числа $n,m$ и $k(1\le n,m\le 100,1\le k\le 10000)$, где $n$ — число вершин во множестве $A$, $m$ — число вершин в множестве $B$, а $k$ — количество рёбер в графе. Каждая из следующих $k$ строк содержит по два числа $u_i$ и $v_i$, обозначающих, что вершина $u_i$ из множества $A$ соединена с вершиной $v_i$ из множества $B$. Вершины во множествах $A$ и $B$ нумеруются независимо, начиная с единицы. Все входные числа целые.

Выходные данные

В первой строке выведите количество $l$ рёбер в максимальном паросочетании. Далее выведите $l$ строк, каждая из которых содержит два числа: $a$ и $b$, где $a$ — вершина из множества $A$, а $b$ — соответствующая ей вершина из множества $B$ в паросочетании. Взятые рёбра должны образовывать максимальное паросочетание.

Примеры