Fie un graf neorientat cu N noduri și M muchii, care NU este conex.

Cerinţe

Să i se adauge grafului un număr minim de muchii, astfel încât acesta să devină conex.

Fie $extra_i$ numărul de muchii nou-adăugate care sunt incidente cu nodul i, iar max_extra cea mai mare dintre valorile $extra_1, extra_2,... , extra_N$. Mulțimea de muchii adăugate trebuie să respecte condiția ca valoarea max_extra să fie minimă.

Date de intrare

Pe prima linie a fișierului de intrare conexidad.in se află două numere naturale N și M, iar pe fiecare dintre următoarele M linii se află câte o pereche de numere a, b, semnificând faptul că există muchia [a,b]. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieşire

Fișierul de ieșire conexidad.out va conține pe prima linie valoarea max_extra. Pe a doua linie va conține valoarea K reprezentând numărul de muchii nou-adăugate în graf. Fiecare dintre următoarele K linii va conține câte o pereche de numere c, d, separate prin câte un spațiu, semnificând faptul că se adaugă grafului muchia [c,d].

Restricţii și precizări

• 1 ≤ N ≤ 100
• 0 ≤ M ≤ N*(N-1)/2
• Nodurile grafului sunt numerotate de la 1 la N inclusiv.
• Muchiile prezente în fișierul de intrare sunt distincte.
• Pentru orice muchie [a,b] aflată în fișierul de intrare, avem a≠b.
• Graful din fișierul de intrare nu este conex.
• În cazul în care soluția afișată pentru un anumit test conectează graful cu număr minim de muchii, dar nu minimizează valoarea lui max_extra, se vor acorda 50% din punctajul pentru testul respectiv.
• Dacă există mai multe soluţii optime, se va admite oricare dintre acestea.
• Se acordă 10 puncte din oficiu.

Exemple

conexidad.in

4 2
1 2
4 2

conexidad.out

1
1
3 1

conexidad.in

5 1
3 4

conexidad.out

2
3
1 3
2 3
4 5

Explicații

Pentru primul test:
Graful este format din două componente conexe, cu noduri din mulțimea {1,2,4} respectiv nodul izolat 3.
După adăugarea muchiei (3,1) vom avea valorile $extra_1=1, extra_2=0, extra_3=1, extra_4=0$, deci max_extra=1.
Se poate demonstra că nu există soluție cu max_extra<1.

Pentru al doilea test:
Graful este format din patru componente conexe, cu noduri din mulțimea {3,4}, respectiv nodurile izolate 1, 2 și 5.
După adăugarea muchiilor (1,3), (2,3) și (4,5), vom avea valorile $extra_1=1, extra_2=1, extra_3=2, extra_4=1, extra_5=1$, deci max_extra=2.
Se poate demonstra că nu există soluție cu max_extra<2.