Plimbare3

plimbare3

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

_“Walking through the city […] I just have to find my way”_
MIron, plictisit de viaţa de zi cu zi, a hotărât să iasă la plimbare în oraşul său natal, Deva. Acesta are o structură de arbore (graf neorientat aciclic conex), fiind format din $N$ pieţe şi $N–1$ străzi ce le conectează. MIron doreşte  să îşi aleagă o piaţă din care să îşi înceapă plimbarea, şi să parcurgă un drum cât mai lung în oraş, fără să treacă prin aceeaşi piaţă de două ori (pentru a nu se plictisi şi mai mult).

“Walking through the city […] I just have to find my way”
MIron, plictisit de viaţa de zi cu zi, a hotărât să iasă la plimbare în oraşul său natal, Deva.  Acesta are o structură de arbore (graf neorientat aciclic conex), fiind format din N pieţe şi N–1 străzi ce le conectează. MIron doreşte  să îşi aleagă o piaţă din care să îşi înceapă plimbarea, şi să parcurgă un drum cât mai lung în oraş, fără să treacă prin aceeaşi piaţă de două ori (pentru a nu se plictisi şi mai mult).

Deoarece MIron este prieten bun cu primarul oraşului, îi poate cere acestuia să mute o stradă, eliminând-o dintre pieţele pe care le conectează momentan, şi adăugând-o între alte două pieţe, astfel încât să se menţină proprietatea de arbore a oraşului Deva.
Ştiind că MIron poate apela la primar pentru mutarea unei singure străzi, voi trebuie să determinaţi lungimea maximă pe care o poate avea drumul lui MIron.

Deoarece MIron nu ştie pe care stradă să o ceară mutată, el vrea să afle lungimea maximă a drumului ce se poate forma pentru fiecare din cele $N-1$ cereri posibile.

Deoarece MIron nu ştie pe care stradă să o ceară mutată, el vrea să afle lungimea maximă a drumului ce se poate forma pentru fiecare din cele N-1 cereri posibile.

h2. Date de intrare

Pe prima linie a fişierului $plimbare.in$ se află un număr întreg $N$, reprezentând numărul de pieţe din oraşul Deva.
Pe următoarele $N-1$ linii se află descrise străzile oraşului, fiecare din aceste linii fiind formate din două numere $x$ şi $y$ reprezentând faptul că există o stradă între pieţele $x$ şi $y$.

Pe prima linie a fişierului plimbare.in se află un număr întreg N, reprezentând numărul de pieţe din oraşul Deva.
Pe următoarele N-1 linii se află descrise străzile oraşului, fiecare din aceste linii fiind formate din două numere x şi y reprezentând faptul că există o stradă între pieţele x şi y.

h2. Date de ieşire

Fişierul de ieşire $plimbare.out$ va conţine $N-1$ linii. Pe cea de-a $i$-a din aceste linii se află lungimea drumului maxim dacă s-ar muta cea de-a $i$-a stradă din fişierul de intrare.

Fişierul de ieşire plimbare.out va conţine N-1 linii. Pe cea de-a i-a din aceste linii se află lungimea drumului maxim dacă s-ar muta cea de-a i-a stradă din fişierul de intrare.

h2. Restricţii

* $1 ≤ N ≤ 200.000$
* $1 ≤ x, y ≤ N$
* Lungimea drumului între două pieţe reprezintă numărul de străzi ce trebuie parcurse pentru a ajunge dintr-o piaţă în cealaltă, fără a trece printr-o piaţă de mai multe ori.

1 <= N <= 200.000
1 <= x, y <= N
lungimea drumului între două pieţe reprezintă numărul de străzi ce trebuie parcurse pentru a ajunge dintr-o piaţă în cealaltă, fără a trece printr-o piaţă de mai multe ori.

h2. Exemplu

h3. Explicaţie

Putem lăsa strada (1, 2) la locul ei, obţinând drumul (2, 1, 3, 4).
Strada (1, 3) se poate muta între pieţele 2 şi 4, obţinându-se drumul  (1, 2, 4, 3, 5).
Strada (4, 3) se poate muta între pieţele 5 şi 4, obţinându-se drumul  (2, 1, 3, 5, 4).
Strada (5, 3) se poate muta între pieţele 4 şi 5, obţinându-se drumul  (2, 1, 3, 4, 5).

Putem lăsa strada (1,2) la locul ei, obţinând drumul (2,1,3,4).
Strada (1,3) se poate muta între pieţele 2 şi 4, obţinându-se drumul  (1,2,4,3,5).
Strada (4,3) se poate muta între pieţele 5 şi 4, obţinându-se drumul  (2,1,3,5,4).
Strada (5,3) se poate muta între pieţele 4 şi 5, obţinându-se drumul  (2,1,3,4,5).

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

9054