Məsələlər
Match them up
Match them up
В этой задаче вам придётся искать максимальное паросочетание. Да не простое, а лексикографически минимальное.
Дан двудольный граф из \textbf{N} вершин в левой доле, \textbf{N} вершин в правой доле и \textbf{K} рёбер между ними.
Максимальное паросочетание --- максимальное по мощности подмножество рёбер графа \textbf{M}, такое, что любая вершина графа инцидентна не более чем одному ребру из \textbf{M}.
Пусть множество рёбер \{(\textbf{u_i}, \textbf{v_i})\} --- максимальное паросочетание, где \textbf{u_i} --- вершины из левой доли, \textbf{v_i} ---вершины из правой доли. Выпишем все вершины в одну последовательность в порядке: \textbf{u_1}, \textbf{v_1}, \textbf{u_2}, \textbf{v_\{2 \}},..., \textbf{u_m}, \textbf{v_m}.
Найдите максимальное паросочетание с лексикографически минимальной такой последовательностью вершин.
\InputFile
В первой строке находится два числа \textbf{n }(\textbf{1} ≤ \textbf{n }≤ \textbf{10^3}) и \textbf{k} (\textbf{0 }≤ \textbf{k }≤ \textbf{10^5})\textbf{ - }количество вершин в каждой из долей и количество рёбер. Далее \textbf{k }строк с описанием рёбер. Каждое ребро описывается парой чисел \textbf{a_i} и \textbf{b_i} (\textbf{1 }≤ \textbf{a_i}, \textbf{b_i} ≤ \textbf{n}), где \textbf{a_i} - вершина из левой доли, а \textbf{b_i} - из правой доли.
\OutputFile
В первой строке выведите размер максимального паросочетания \textbf{m}. Далее \textbf{m} строк по два числа \textbf{u_i}, \textbf{v_i} в каждой, где \textbf{u_i} - вершина из левой доли, а \textbf{v_i} --- вершина из правой доли, соответствующие \textbf{i}-ому ребру паросочетания.
Giriş verilənləri #1
3 5 1 2 1 3 3 2 2 3 2 1
Çıxış verilənləri #1
3 1 3 2 1 3 2