JHIO 2022. 3. zadatak

U jednom maloj državi živi Stjepan, čovjek koji mrzi raskrižja. Stjepan je nedavno postao apsolutni vladar države te je odlučio da će prva stvar koju će napraviti na vlasti biti uništavanje cesta kako više ne bi bilo raskrižja.

Država se sastoji od N gradova i N-1 cesta između gradova. Između svaka dva grada moguće je doći nekim jedinstvenim nizom cesta. Stjepan sada želi uništiti neke ceste tako da nakon uništavanja svaki grad ima iz sebe najviše dvije ceste.

Iako će uništavati ceste, Stjepan je dobar čovjek i ne želi puno problema pa će uništiti najmanji mogući broj cesta tako da ostvari svoj cilj. Odredite broj cesta koje će Stjepan uništiti.

Ulazni podaci

U prvom je retku prirodan broj N (2 ≤ N ≤ 100000), broj gradova.

U sljedećih N-1 redaka nalaze se dva različita prirodna broja A i B (1 ≤ A, B ≤ N), oznake gradova koje spaja i-ta cesta.

Izlazni podaci

U prvi redak ispiši traženi broj iz zadatka.

Probni primjeri

Ulaz

5
1 2
1 3
2 4
2 5

Izlaz

1

Opis prvog probnog primjera: Stjepan može npr. uništiti cestu između grada 1 i grada 2

Ulaz

7
1 2
1 3
2 4
2 5
3 6
3 7

Izlaz

2