Tree Game

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Alice and Bob are playing the game. Initially, there is a single rooted tree. Players take turns alternately, Alice starts.
In a single turn, Alice should choose any nonempty subset of roots of tree (or trees) and remove them. On the other hand, Bob should choose any nonempty subset of leafs and remove them from the tree (or trees). (Please note that Bob always takes some of the deepest in the original tree leafs.) It's not allowed to skip the turn. The game ends when a player can't take a turn.
The Alice's goal is to minimize the number of turns made by the both players, while Bob wants this number to be the maximal. Considering they both play optimally, what is the number of turns eventually made?
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of nodes of the tree.
The next N1 lines contain pairs of nodes' numbers U_{i} and V_{i} (one pair per line), denoting the edges of the tree.
The nodes are numbered from 1 to N, inclusive, and the node with the index 1 is the root of the tree.
Output
For each test case, output a single line containing the answer to the corresponding test case.
Constraints
 1 ≤ T ≤ 40
 1 ≤ N ≤ 10000
 1 ≤ U_{i}, V_{i} ≤ N
Example
Input: 3 2 1 2 7 1 3 1 4 4 2 4 5 4 6 6 7 1 Output: 2 5 1
Author:  witua 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/TREEGAME 
Tags  cook49, easy, games, greedy, pointers, witua 
Date Added:  14042014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 