CSES - Pikajunat
  • Time limit: 1.00 s
  • Memory limit: 128 MB

Bittimaassa on n kaupunkia, joiden välillä on junayhteyksiä. Jokaisesta kaupungista toiseen kaupunkiin on olemassa yksikäsitteinen reitti.

Tehtäväsi on rakentaa mahdollisimman monta pikajunayhteyttä. Voit muuttaa minkä tahansa yhteyden pikajunaksi, mutta samasta kaupungista voi lähteä korkeintaan yksi pikajuna toiseen kaupunkiin.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: kaupunkien määrä. Kaupungit on numeroitu 1,2,\ldots,n.

Sitten syötteessä on n-1 riviä, jotka kuvaavat junayhteydet. Jokaisella rivillä on kaksi kokonaislukua a ja b: kaupunkien a ja b välillä on yhteys. Kaikki yhteydet ovat kaksisuuntaisia.

Tuloste

Tulosta yksi kokonaisluku: suurin mahdollinen määrä pikajunayhteyksiä.

Rajat

  • 1 \le n \le 10^5

Esimerkki

Syöte:

5
1 2
2 3
2 4
4 5

Tuloste:

2