Scrooge Minho 2

Minho, known for pinching every coin, rules the country of Cheon, which has $N$ cities. To keep the cost of building roads down he built only $N - 1$ roads, so between any two cities there is exactly one route along the roads. Every road is bidirectional.

With the cities finished, Minho now turns to police stations. Putting one in every city is too expensive for him, so he will build them in only some cities. He worries that the citizens will revolt if any city or any road is left unwatched.

A police station built in a city watches that city, every city joined to it by a single road, and every road that touches it. So a road is watched when at least one of its two endpoint cities has a station, and a city is watched when the city itself or one of the cities joined to it by a single road has a station.

Find the smallest number of cities that need a police station so that every city and every road is watched.

The first line contains the number of cities $N$ ($2 \le N \le 100000$).

Each of the next $N - 1$ lines describes one road with two integers $u$ and $v$ ($1 \le u, v \le N$, $u \ne v$) separated by a space, meaning city $u$ and city $v$ are joined by a road. The roads always form a tree.

Print the smallest number of cities that need a police station.