Максимальне паросполученя
Максимальне паросполученя
Граф (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. Взяті ребра повинні утворити максимальне паросполучення.
2 3 4 1 1 1 2 2 2 2 3
2 1 1 2 3