Journey

Interview

Time limit2sMemory limit1024 MB

Summary

Given a tree of n cities, find the fewest new roads to add so that a route visits every city once and returns to the capital.

Level: Medium6 of 10
Topics: Tree, Greedy
Solved: No attempts yet

Problem

Flatland has $n$ cities, and some of them are connected by two-way roads. The road network is set up so that there is exactly one way to travel from any city to any other city. The king of Flatland wants to make a trip through Flatland that visits each city exactly once and returns to the capital. He also does not want to travel along any road more than once.

The transport minister tried to explain that this is impossible, since the road network of Flatland has no cycles. The king insisted on the trip anyway, so new roads must be built.

Help the road construction minister find the minimum number of roads that must be built so that the king can make his trip.

Input

The first line contains the number of cities $n$ ( $3 \le n \le 100\,000$ ). Each of the next $n-1$ lines contains two integers, the numbers of the cities connected by a road. The cities are numbered from 1 to $n$ .

Output

Print one number, the minimum number of roads that must be built.

Hint

In the sample, for example, roads 3-4 and 4-5 can be built. Then the king can travel along the route 1-2-3-4-5-1.

Examples1

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