21832_Arres

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.

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 )

For each case output the minimal number of policemen.

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

1
3