F :: Finding loop

Time Limit: 1 Second    Memory Limit: 65536 KB

 There is bad news! Piloop has been lost. However, Poopi and Mj are trying to find him before the local contest so he can be present at the contest. Poopi knows that Piloop has been last seen in Parks City. Therefore, Poopi and MJ have analyzed the city’s map thoroughly before actually going there. There are N parks within the city and Piloop is waiting in front of one of these parks for his friends to find him. But they do not exactly know which one. There are some of bidirectional roads in the city each connecting two  different  parks  together.  Moreover,  the  city  is  designed  in  a  way  that  there  is  exactly  one  simple path between each pair of parks.  

Now, Poopi and MJ have planned to use the following strategy. They both meet at some park S and plan for the search. In the search plan each of them chooses a path such that union of the paths covers all parks. Both paths end at park T where the three old friends gather together again. Traversing each road needs  one  unit  of  time  and  since  Piloop  is  waiting  in  front  of  the  park,  Poopi  and  Mj  do  not  have  to search the park itself to find him. 

For each starting park S the minimum time to complete the search is called the searching time for that park.  Since  Poopi  and  MJ  are  too  busy  with  preparing  the  problemset  of  AUT  local  contest  they  are asking you to find out the park with minimum search time and calculate its search time.

 

Input

In the first line there is an integer T (T ≤ 100), the number of tests. Each test begins with an integer N (1 ≤ N ≤ 1000), the number of parks in the city. Next N‐1 lines are streets of Parks City, each of which is a pair of integers u, v (1 ≤ u, v ≤ N, u ≠ v) meaning that there is a bidirectional street between park u and park v. It is guaranteed there is exactly one simple path between each pair of parks. 

 

Output

For each test print two integers in a single line separated by a single space, number of the park with the minimum searching time and it’s searching time. If there are multiple parks with the minimum searching time, output the one with the smallest number. 

 

Sample Input

1
5
1 2
4 1
2 5
1 3

Sample Output

1 4

Submit

Source: AUT 2012