plimbare

Cerință

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

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

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.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq x, y \leq 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.

Exemplu

plimbare.in

5
1 2
1 3
4 3
5 3

plimbare.out

3
4
4
4

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