Граф (V, E) називається двудольним, якщо множину його его вершин V можна розбити на дві підмножини A і B такі, що будь-яке ребро із E з'єднує вершину із A з вершиною із B.

Паросоплученя P називається будь-яка підмножина E така, що ніякі два ребра із нього не має спільної вершини.

Максимальне паросполученя - це паросполученя, кількість ребер в якому максимальна.

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

Вхідні дані

В першому рядку задано три числа n, m і k (1 ≤ n, m ≤ 100, 1 ≤ k ≤ 10000), де n - кількість вершин в множині A, m - кількість вершин в B, а k - кількість ребер в графі. Кожен з наступних k рядків містить по два числа ui і vi, означає, що вершина ui множини A з'єднана ребром з vi множини B. Вершини у множинах A і B нумеруються окремо, починаючи з одиниці. Всі вхідні числа цілі.

Вихідні дані

В першому рядку виведіть кількість l ребер в максимальному паросполучені. Далі виведіть l рядків, по два числа в кожному. Числа aj і bj, що стоять в j-ой із цих рядків, означає, що паросполученя взято між вершиною aj множини A і вершиною bj множини B. Взяті ребра повинні утворити максимальне паросполучення.