Match them up
В этой задаче вам придётся искать максимальное паросочетание. Да не простое, а лексикографически минимальное.
Дан двудольный граф из n вершин в левой доле, n вершин в правой доле и k рёбер между ними.
Максимальное паросочетание - это максимальное по мощности подмножество рёбер графа m, такое, что любая вершина графа инцидентна не более чем одному ребру из m.
Пусть множество рёбер {(u_i, v_i)} — максимальное паросочетание, где u_i — вершины из левой доли, v_i —вершины из правой доли. Выпишем все вершины в одну последовательность в порядке: u_1, v_1, u_2, v_{2 },..., u_m, v_m.
Найдите максимальное паросочетание с лексикографически минимальной такой последовательностью вершин.
Входные данные
В первой строке находится два числа n (1 ≤ n ≤ 10^3) и k (0 ≤ k ≤ 10^5) - количество вершин в каждой из долей и количество рёбер. Далее k строк с описанием рёбер. Каждое ребро описывается парой чисел a_i и b_i (1 ≤ a_i, b_i ≤ n), где a_i - вершина из левой доли, а b_i - из правой доли.
Выходные данные
В первой строке выведите размер максимального паросочетания m. Далее m строк по два числа u_i, v_i в каждой, где u_i - вершина из левой доли, а v_i — вершина из правой доли, соответствующие i-ому ребру паросочетания.