CSES - Etäisyydet I
  • Time limit: 1.00 s
  • Memory limit: 512 MB
Annettuna on puu, jossa on $n$ solmua. Tehtäväsi on laskea jokaiselle puun solmulle suurin etäisyys johonkin toiseen solmuun.

Syöte

Ensimmäisellä rivillä on kokonaisluku $n$: solmujen määrä. Solmut on numeroitu $1,2,\dots,n$.

Sitten syötteessä on $n-1$ riviä, jotka kuvaavat kaaret. Jokaisella rivillä on kaksi kokonaislukua $a$ ja $b$: solmujen $a$ ja $b$ välissä on kaari.

Tuloste

Tulosta $n$ kokonaislukua: jokaiselle solmulle $1,2,\dots,n$ suurin etäisyys toiseen solmuun.

Rajat
  • $1 \le n \le 5 \cdot 10^5$
  • $1 \le a,b \le n$
Esimerkki

Syöte:
5
1 2
1 3
3 4
3 5


Tuloste:
2 3 2 3 3