Scrooge Minho 2

Interview

Time limit2sMemory limit512 MB

Summary

Given a tree with N cities, place the fewest police stations so that every city and every road is covered, where a station covers its city, its neighbors, and all incident roads.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, DFS, Greedy
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples8

Example 1
Input
```
5
4 5
4 2
2 3
1 2
```
Expected output
```
2
```
Example 2
Input
```
2
1 2
```
Expected output
```
1
```
Example 3
Input
```
3
2 1
2 3
```
Expected output
```
1
```
Example 4
Input
```
6
1 2
1 3
1 4
1 5
1 6
```
Expected output
```
1
```
Example 5
Input
```
6
1 2
2 3
3 4
4 5
5 6
```
Expected output
```
3
```
Example 6
Input
```
7
1 2
2 3
3 4
4 5
5 6
6 7
```
Expected output
```
3
```

Example 7

Input

Expected output

Example 8

Input

Expected output