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

Граф $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$ в паросполученні. Обрані ребра повинні утворювати максимальне паросполучення.

Приклади