== include(page="template/taskheader" task_id="amici2") ==
În cadrul Comisiei de la clasele $11-12$ a apărut, în mod natural, o reţea de socializare. Iniţial între cei $N$ membri ai Comisiei există $M$ relaţii de prietenie. În fiecare zi, se formează noi asemenea relaţii după următoarea regulă: dacă membrul $A$ nu este încă prieten cu membrul $B$, dar ei au cel puţin un prieten în comun, atunci $A$ şi $B$ vor deveni prieteni în ziua imediat următoare. Această socializare intensă va naşte, bineînţeles, multe poveşti şi anecdote care le vor înveseli în mod cert viitoarele întâlniri. Din păcate, autorul este insensibil la această latură umanistă a activităţii comisiei şi insistă că situaţia prezintă, este de fapt doar o oportunitate pentru o provocare algoritmică. El se întreabă câte zile va dura până când orice membru al comisiei va deveni prieten cu orice alt membru. Deoarece comisia are multi membri anul acesta, iar autorul nu are, de fel, standarde foarte ridicate, acesta se multumeste cu o aproximare a rezultatului. Mai exact, dacă răspunsul adevărat este $X$, atunci răspunsurile $X + 1$ sau $X – 1$ sunt considerate şi ele acceptabile.
În cadrul Comisiei de la clasele $11-12$ a apărut, în mod natural, o reţea de socializare. Iniţial între cei $N$ membri ai Comisiei există $M$ relaţii de prietenie. În fiecare zi, se formează noi asemenea relaţii după următoarea regulă: dacă membrul $A$ nu este încă prieten cu membrul $B$, dar ei au cel puţin un prieten în comun, atunci $A$ şi $B$ vor deveni prieteni în ziua imediat următoare. Această socializare intensă va naşte, bineînţeles, multe poveşti şi anecdote care le vor înveseli în mod cert viitoarele întâlniri. Din păcate, autorul este insensibil la această latură umanistă a activităţii comisiei şi insistă că situaţia prezintă, de fapt doar o oportunitate pentru o provocare algoritmică. El se întreabă câte zile va dura până când orice membru al comisiei va deveni prieten cu orice alt membru. Deoarece comisia are multi membri anul acesta, iar autorul nu are, de fel, standarde foarte ridicate, acesta se multumeste cu o aproximare a rezultatului. Mai exact, dacă răspunsul adevărat este $X$, atunci răspunsurile $X + 1$ sau $X – 1$ sunt considerate şi ele acceptabile.
h2. Cerinta
Dându-se numerele N şi M, cât şi cele M relatii de prietenie dintre membrii comisiei, să se estimeze câte zile trebuie să treacă până când există relatie de prietenie între oricare doi membri ai comisiei.
Dându-se numerele $N$ şi $M$, cât şi cele $M$ relatii de prietenie dintre membrii comisiei, să se estimeze câte zile trebuie să treacă până când există relatie de prietenie între oricare doi membri ai comisiei.
h2. Date de intrare
Pe prima line a fisierului "amici2.in" se va afla numărul $T$, reprezentând numărul de teste din fişier, fiecare test respectând următorul format:
Pe prima line a fisierului $amici2.in$ se va afla numărul $T$, reprezentând numărul de teste din fişier, fiecare test respectând următorul format:
Prima linie conţine două numere naturale $N$ şi $M$, cu semnificaţia din enunţ. Următoarele $M$ linii vor conţine câte două numere $X$ şi $Y$, semnficând faptul că $X$ şi $Y$ sunt prieteni iniţial. O anumită pereche $X$ $Y$ se poate repeta în cadrul fisierului de intrare.
h2. Date de ieşire
În fişierul de ieşire $amici2.out$ ...
În fişierul $amici2.out$ se vor afişa $T$ linii, fiecare conţinând răspunsul pentru câte un test în ordinea în care sunt date testele.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1$ ≤ $N$ ≤ $21.000$
* $0$ ≤ $M$ ≤ $41.000$
* $1$ ≤ $T$ ≤ $5$
h2. Exemplu
table(example). |_. amici2.in |_. amici2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 2
3 2
1 2
1 3
5 4
3 1
1 2
2 4
2 5
| 1
2
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="amici2") ==
