CSES - Läpimitta
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Annettuna on puu, jossa on n solmua. Tehtäväsi on laskea puun läpimitta eli kuinka pitkä on pisin puussa oleva polku.

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 yksi kokonaisluku: puun läpimitta.

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:

3

Selitys: Läpimittaa vastaa esimerkiksi polku 2 \rightarrow 1 \rightarrow 3 \rightarrow 5.