All submissions for this problem are available.
The country of Codeland contains N cities and N - 1 bidirectional roads between them such that there is a path between any two cities. The roads in Codeland were built long ago and now they are in need of repair. You have been hired to repair all the roads. You intend to do this by dispatching robots on some of the roads. Each robot will repair the road he is currently on and then move to one of the adjacent unrepaired roads. After repairing that, he will move to another adjacent unrepaired road, repair that and so on.
Two roads are adjacent if they have the same city at one of their endpoints. For the process to be efficient, no two robots can ever repair the same road, and no road can be visited twice. What is the least number of robots needed to accomplish the task?
The first line contains the number of test cases T. T test cases follow. The first line of each testcase contains N, the number of cities in Codeland. The cities are numbered 0..N - 1. The following N - 1 lines contain the description of the roads. The ith line contains two integers ai and bi, meaning that there is a road connecting cities with numbers ai and bi.
Output T lines, one corresponding to each test case containing the required answer for that test case.
1 <= T <= 20
1 <= N <= 10000
0 <= ai,bi < N
Input: 3 4 0 1 0 2 0 3 6 0 1 1 2 2 3 2 4 4 5 7 0 1 1 2 2 3 2 4 4 5 3 6 Output: 1 1 2
|Time Limit:||0.389646 - 1.94823 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, GO, NODEJS|
Fetching successful submissions
If you are still having problems, see a sample solution here.