Migrated from Lutece 596 KuFeng's Defense

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

God Wu is a militant leader. Now he declared war on to the Gensokyo. As Gensokyo’s ruler, King Kufeng decides to build an emergency network.

As we all know, Gensokyo consist of $N$ area, each two areas are connected and there is only one road from area $A$ to area $B$($A\neq B$). It’s common sense that the Gensokyo’s entrance is the Hakurei Shrine. But God Wu has space leaping ability. So King Kufeng decide to send troops to some area. Which let each area has the army or one of its directly adjacent area has the army.

Input

There are several test cases.

For each test case, the first line is an integer $N$($1\leq N\leq 10000$) which describes the number of area. The next $N-1$ line describes both ends of the one road(undirected).

Output

For each test case output a line with an integer representing the minimal number area King Kufeng need to send troops.

Samples

5
1 3
5 2
4 3
3 5

2

Resources

UESTC Training for Dynamic Programming