== include(page="template/taskheader" task_id="conexidad") ==

Poveste şi cerinţă...

Fie un graf neorientat cu $N$ noduri şi $M$ muchii, care NU este conex.
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ă.

h2. Date de intrare

Fişierul de intrare $conexidad.in$ ...

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.

h2. Date de ieşire

h2.  Date de ieşire

În fişierul de ieşire $conexidad.out$ ...

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

h2. Restricţii

h2. 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 &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.
 
h2. Exemple
 
table(example).
|_. conexidad.in
|_. conexidad.out
|_. Explicatii si comentarii
|
| 4 2
1 2
4 2
| 1
1
3 1
| 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.
|
| 5 1
3 4
| 2
3
1 3
2 3
4 5
| 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.
|

h2. Exemplu
 
table(example). |_. conexidad.in |_. conexidad.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...
 
== include(page="template/taskfooter" task_id="conexidad") ==
 

== include(page="template/taskfooter" task_id="conexidad") ==