Transmitters

Interview

Time limit2sMemory limit1024 MB

Summary

Given a tree of chambers, find the fewest Wi-Fi transmitters so every tunnel is covered by a transmitter at an endpoint or two transmitters next to it.

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

Statement

Bajtazar has become the new director of a historic salt mine. To attract more tourists, he wants to install wireless internet in the mine's tunnels.

The mine has $n$ chambers connected by $n - 1$ tunnels. You can walk from any chamber to any other chamber through the tunnels. Bajtazar wants to place Wi-Fi transmitters in the chambers so that internet is available in every tunnel. To use the internet in the tunnel connecting chambers $a$ and $b$ , at least one of the following must hold:

There is a transmitter in chamber $a$ or in chamber $b$ .
The set of chambers reachable from $a$ or $b$ using at most one tunnel contains at least two transmitters.

Find the minimum number of transmitters Bajtazar must place. Any number of transmitters can be placed in a single chamber.

Input

The first line contains a positive integer $n$ , the number of chambers. Chambers are numbered from 1 to $n$ .

Each of the next $n - 1$ lines contains two integers $a$ and $b$ ( $1 \le a, b \le n$ , $a \ne b$ ) separated by a single space, meaning chambers $a$ and $b$ are connected by a tunnel.

Output

The first and only line of the standard output should contain one integer, the minimum number of transmitters Bajtazar must place.

Constraints

$n \le 200\,000$

Examples2

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