URI Online Judge | 2079

War Product

By XII Maratona de Programação IME-USP, 2008 BR Brazil

Timelimit: 1

The International Committee of the Red Cross, non-profit organization whose goal is to defend and protect the victims of wars (or rather victims of capital) or natural disasters, won the Nobel Prize in 1917, 1945 and 1963 by their extremely important job. As you might imagine, the Red Cross has always had problems walking in the midst of war. Many links (roads, railways, etc.) between cities of countries at war can be destroyed by bombing or ruled by tyrants.

The intelligence department of the Red Cross is committed to creating a computer program to assist the operations of the Red Cross in the future. The idea is, given a map of the region that will be helped, determine which cities the bases of the Red Cross should be made. Initially, the Department is interested in testing the first version of the program in cities with the following characteristics: (a) there is always a path between two cities which passes through one or more links; (b) There are no two different paths between any two cities. Despite the Red Cross resources are usually limited, they want to choose the largest possible number of basis, and ensure that there is a base in the town or there is a base in a neighboring town, with the additional restriction that is not allowed to create bases in two neighboring cities. This last constraint is given by the fact that if we were at war period, the Red Cross, as we should have free access in cities, and with it the suspicion of spying may arise, which may compromise the main goal of the organization.

Your task is to write the first version of the program that the Department wants to test.


The first line of a test case has an integer T which indicates the number of following instances.

The first line of each instance has an integer N (1 ≤ N ≤ 6000) indicating the number of cities on the map. Cities are identified by 1, 2, ..., N. The next N-1 lines contain two integers u and v (1 ≤ u, vN, uv) indicating a link between cities u and v (consider that such connections allow access from u to v and from v to u).


For each instance print an integer indicating the maximum number of bases that the Red Cross can build taking into consideration the restrictions described above.

Sample Input Sample Output

1 2
1 3
2 4
2 5
2 6
3 7
7 8
7 9
7 10
1 2
1 3
2 4
2 5