Onları uyğunlaşdırın
Bu tapşırıqda sizdən maksimum uyğunluğu tapmaq tələb olunur. Lakin, bu uyğunluq leksikoqrafik olaraq minimal da olmalıdır.
İki tərəfli qraf verilmişdir: sol tərəfdə N təpə, sağ tərəfdə N təpə və onların arasında K kənar mövcuddur.
Maksimum uyğunluq, qrafın M kənarlarının gücünə görə maksimum olan alt çoxluğudur ki, burada qrafın istənilən təpəsi M-dən ən çox bir kənara insidentdir.
Qoy kənarların çoxluğu {(u_i, v_i)} — maksimum uyğunluq olsun, burada u_i — sol tərəfdəki təpələr, v_i — sağ tərəfdəki təpələrdir. Bütün təpələri bir ardıcıllıqla yazacağıq: u_1, v_1, u_2, v_2, ..., u_m, v_m.
Leksikoqrafik olaraq minimal olan belə bir təpə ardıcıllığı ilə maksimum uyğunluğu tapın.
Giriş verilənləri
Birinci sətirdə iki ədəd N və K — hər tərəfdəki təpələrin sayı və kənarların sayı verilir. Sonra K sətir kənarların təsviri ilə gəlir. Hər kənar a_i və b_i ədədləri ilə təsvir olunur, burada a_i — sol tərəfdəki təpə, b_i — sağ tərəfdəki təpədir.
Çıxış verilənləri
Birinci sətirdə maksimum uyğunluğun ölçüsünü m çıxarın. Sonra m sətir, hər birində iki ədəd u_i, v_i, burada u_i — sol tərəfdəki təpə, v_i — uyğunluğun i-ci kənarına uyğun gələn sağ tərəfdəki təpədir.
Məhdudiyyətlər
1 ≤ N ≤ 10^3
0 ≤ K ≤ 10^5
1 ≤ a_i, b_i ≤ N