Arrest

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 3069
64-bit integer IO format: %I64d      Java class name: Main

Description

Country ALPC has n cities, and the cities are connected by undirected roads. Furthermore, there is exactly one route between each pair of cities. Now some criminals break the prison and the police do not know where they are. And the criminals can stay in a city or move on the roads. The police office has made a decision to send policemen to arrest the breakers. If a police and a criminal at a same point at the same time the criminal is under arrest, no matter in a city or on a road. The police office wants to minimize the number of policemen to arrest all the criminals. Now the map of Country ALPC is given, please tell the police office the least number of policemen required.

Input

There are several test cases.
The first line a integer n, the number of cities. Next n-1 lines each two integers a and b, there is a road between city a and city b.
(1<=n <= 1000, 1 <= a, b <= n)

Output

For each case output the minimal number of policemen.

Sample Input

3
1 2
2 3
16
1 2
1 3
1 4
5 6
5 7
10 8
8 11
9 12
9 13
14 1
14 15
15 16
15 8
9 16
14  5

Sample Output

1
3

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .