31156번 - Amazing Tree 다국어

문제

Consider an undirected tree. The following algorithm constructs a post-order traversal of the tree:

fun dfs(v):
 mark v as used
 for u in neighbours(v):
 if u is not used:
 dfs(u)
 append v to order

The post-order traversal will be in the list order.

You are allowed to choose the order of neighbors for each vertex as well as the starting vertex. What is the lexicographically minimal order you can get?

입력

The first line of input contains one integer $T$ (1ドル \le T \le 10^{5}$) --- the number of test cases you need to process. Description of the test cases follows.

The first line of each test case contains a single integer $n$ (2ドル \le n \le 2 \cdot 10^{5}$) --- the number of vertices in the tree.

The $i$-th of the next $n-1$ lines contains two integers $u_i, v_i$ (1ドル \le u_i, v_i \le n,ドル $u_i \ne v_i$), meaning that there is an undirected edge $(u_i, v_i)$ in the tree. It is guaranteed that the given graph is a tree.

The sum of $n$ over all test cases in one test file does not exceed 2ドル \cdot 10^{5}$.

출력

For each test case print the lexicographically minimal order on a separate line.

제한

노트

The first test looks as follows:

By starting in vertex 1ドル$ we can only get order 2ドル\ 3\ 1$. By starting in vertex 2ドル$ we can only get order 1ドル\ 3\ 2$. By starting in vertex 3ドル$ we can get two orders: 1ドル\ 2\ 3$ and 2ドル\ 1\ 3$. The lexicographically minimal of the four orders is 1ドル\ 2\ 3$.

The second test looks as follows:

By starting in vertex 1ドル$ we can get two orders: 2ドル\ 3\ 1$ and 3ドル\ 2\ 1$. By starting in vertex 2ドル$ we can only get order 3ドル\ 1\ 2$. By starting in vertex 3ドル$ we can only get order 2ドル\ 1\ 3$. The lexicographically minimal of the four orders is 2ドル\ 1\ 3$.

The third test looks as follows:

The lexicographically minimal order is 4ドル\ 5\ 2\ 1\ 6\ 3\ 7$ it can be obtained by starting in node 7ドル$.