23169번 - Mission Impossible: Grand Theft Auto 스페셜 저지다국어

Tom Cruise had his car stolen during the filming in Birmingham. You, as the chief police officer, are asked to catch the thief.

Your people are patrolling the countryside, so the criminal can only be in one of $n$ towns, and the highways between them represent a tree --- that is, there are $n - 1$ bidirectional roads each connecting a pair of towns, and it is possible to traverse from each of them to any other. On each day you can pick any two towns $A$ and $B$ (not necessarily distinct) and request a troop which will check every town on the simple path between $A$ and $B$ (including both of them). If the thief is in one of these towns then it's game over for him. Otherwise, later that night he can move into any other adjacent town by a single road or stay still in the town where he was.

Since this is a very important case, you are very short of time. More specifically, let $m$ be the number of leaves in the tree (that is, towns with only one outgoing road). Then you have to come up with a plan of $\lfloor m/2 \rfloor + 1$ days which catches the thief: for each day you tell the corresponding $A$ and $B$ for this day, and your goal is to catch the guy independently on his actions between the days.

Find a plan satisfying the requirements. You will have to answer several test cases.

The first line of input contains the only integer $T$ ($1 \leq T \leq 100$) --- the number of test cases. $T$ tests follow.

The first line of each test case contains a single integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) --- the number of towns. Each of the next $n - 1$ lines consists of two integers $u$ and $v$ separated by space ($1 \leq u, v \leq n$), denoting a road between towns $u$ and $v$.

It is guaranteed that each test case represents a tree, and that the sum of all $n$ does not exceed $2 \cdot 10^5$.

For each test case, print exactly $\lfloor m/2 \rfloor + 1$ lines, each consisting of two integers $A$ and $B$ ($1 \le A, B \le n$) denoting the endpoints of the corresponding path. If you are sure that you can catch the thief using less operations, just add arbitrary paths at the bottom. One can prove that an answer always exists under these constraints.

Extra lines in the sample output are to visually separate answers for different cases. You do not have to print them.