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

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