Annettuna on puu, jossa on $n$ solmua. Tehtäväsi on etsiä mahdollisimman suuri paritus eli joukko kaaria, jossa jokainen solmu on enintään yhden kaaren päätesolmuna.

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: suurin parituksen koko.

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

Selitys: Yksi mahdollinen ratkaisu on $(1,2)$ ja $(3,4)$.