conexidad

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 \leq N \leq 100$
• $0 \leq M \leq N \cdot (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 \neq 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.

Exemplul 1

conexidad.in

4 2
1 2
4 2

conexidad.out

1
1
3 1

Explicație

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$.

Exemplul 2

conexidad.in

5 1
3 4

conexidad.out

2
3
1 3
2 3
4 5

Explicație

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$.