GCPC11J - Time to live

As you might know, most computer networks are organized in a tree-like fashion, i.e. each computer is reachable by each other computer but only over one, unique path.

The so-called Time to live (TTL) specifies after how many hops a network packet is dropped if it has not reached its destination yet. The purpose of the TTL is to avoid situations in which a packet circulates through the network caused by errors in the routing tables.

The placement of a router that connects the network to another network is optimal when the maximal needed TTL for packets that are sent from this router to any other computer within the same network is minimal. Given a network as specified above, you should calculate the maximal needed TTL in this network if you can select the computer that should be used as router.

Input

The first line of the input consists of the number of test cases c that follow (1 ≤ c ≤ 100). Each test case starts with a line specifying N, the number of computers in this network (1 < N ≤ 105). Computers are numbered from 0 to N-1. Then follow N-1 lines, each specifying a network connection by two numbers a and b which means that computer a is connected to computer b and vice versa, of course (0 ≤ a, b < N).

Output

For each test case in the input, print one line containing the optimal TTL as specified above.

Example

Input:
3
2
1 0
5
3 2
2 1
0 2
2 4
9
3 1
6 5
3 4
0 3
8 1
1 7
1 6
2 3

Output:
1
1
2

Added by:Adrian Kuegel
Date:2011-07-05
Time limit:1.807s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:German Collegiate Programming Contest 2011 (Author: Tobias Werth)

hide comments
2021-08-25 22:56:13 Jean-Ralph Aviles
Don't use recursion. Test cases are crafted to cause a stack overflow.
2021-02-03 16:19:56
Using dfs will go Runtime Error in java (may be due to stackoverflow ), bfs will go AC.
2020-09-22 12:12:41
Can anyone explain this question to me? I did not understand it.
2020-02-22 18:50:32
in my code i'm using a global variable and assigning value to it at the time of declaration and its showing segmentation error but if i'm assigning value to it inside a function then it is working fine?
can somebody tell me what can be the issue?
it is because of this i had wasted my like 3 hours just to rectify the error
2020-02-19 10:43:10
you won't be able to do this go read more
2019-12-13 12:59:04
AC in one go.
2019-07-29 19:35:03
you have to find the radius of the tree
radius of tree = ceil(diameter/2)
2018-12-25 09:47:48
Great (basic) problem to attempt in/out DP for the first time! Diameter finding will work too
2018-11-29 13:40:55
Just find the longest path.As the max hop will be equal (max dist between 2 nodes)/2.
2018-05-28 13:26:05
Use BufferedReader with Adjacency List in Java. Tree Diameter approach.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.