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 і K — кількість вершин у кожній з долей та кількість ребер. Далі K рядків з описом ребер. Кожне ребро описується парою чисел a_i та b_i, де a_i — вершина з лівої долі, а b_i — з правої долі.
Вихідні дані
У першому рядку виведіть розмір максимального паросполучення m. Далі m рядків по два числа u_i, v_i у кожному, де u_i — вершина з лівої долі, а v_i — вершина з правої долі, яка відповідає i-ому ребру паросполучення.
Обмеження
1 ≤ N ≤ 10^3
0 ≤ K ≤ 10^5
1 ≤ a_i, b_i ≤ N