== include(page="template/taskheader" task_id="zvon") ==
Poveste si cerinta...
Directorul unei filiale a unei mari companii a aflat un zvon conform caruia presedintele companiei a decis sa desfiinteze filiala respectiva si sa concedieze toti angajatii filialei (inclusiv pe director). Fiind in relatii bune cu angajatii sai, directorul a decis sa isi anunte angajatii intr-un timp cat mai scurt, pentru ca acestia sa isi poata gasi cat mai repede un alt loc de munca. Angajatii filialei sunt organizati intr-o structura ierarhica arborescenta. In varful ierarhiei se afla directorul, care are cativa subordonati directi. Acestia au la randul lor alti subordonati directi s.a.m.d. pana la cel mai umil angajat, care nu are nici un subordonat. Zvonul concedierii se propaga, astfel, din varful ierarhiei, pana la baza ei. La un minut dupa ce a aflat zvonul, directorul poate da un telefon si isi poate anunta unul din subordonati. Dupa inca un minut, directorul isi poate anunta inca un subordonat, pana cand sunt anuntati toti subordonatii sai. La randul sau, fiecare subordonat, imediat dupa ce afla zvonul, asteapta un minut pana sa isi anunte unul din subordonatii proprii, apoi inca unul pana sa isi anunte un alt subordonat s.a.m.d. Angajatii care nu au subordonati nu anunta pe nimeni. Este evident ca ordinea de anuntare a subordonatilor influenteaza durata de timp dupa care toti angajatii afla zvonul. Determinati durata de timp minima din momentul in care directorul a aflat zvonul, dupa care toti angajatii pot afla zvonul.
h2. Date de intrare
...
Prima linie a fisierului de intrare $zvon.in$ contine numarul intreg $T$, reprezentand numarul de teste. In continuare, urmeaza descrierea celor $T$ teste. Pe prima linie din cadrul fiecarui test se afla numarul intreg $N$, reprezentand numarul de angajati. Urmatoarele $N-1$ linii contin cate doua numere intregi diferite $a$ si $b$, avand semnificatia ca $b$ este un subordonat direct al lui $a$.
h2. Date de iesire
...
Pentru fiecare test afisati in fisierul de iesire $zvon.out$ cate o linie continand durata de timp minima dupa care toti angajatii pot afla zvonul.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 57$
* $1 ≤ N ≤ 100 000$
* Angajatii sunt numerotati de la $1$ (directorul) la $N$.
h2. Exemplu
table(example). |_. zvon.in |_. zvon.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|3
1
3
1 2
1 3
5
1 2
1 3
3 4
3 5
|0
2
3
|
h3. Explicatie
...
== include(page="template/taskfooter" task_id="zvon") ==
