Граф (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 рядків містить по два числа u[i]
і v[i]
, означає, що вершина u[i]
множини A з'єднана ребром з v[i]
множини B. Вершини у множинах A і B нумеруються окремо, починаючи з одиниці. Всі вхідні числа цілі.
В першому рядку виведіть кількість l ребер в максимальному паросполучені. Далі виведіть l рядків, по два числа в кожному. Числа a[j]
і b[j]
, що стоять в j-ой із цих рядків, означає, що паросполученя взято між вершиною a[j]
множини A і вершиною b[j]
множини B. Взяті ребра повинні утворити максимальне паросполучення.