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 may choose the order of neighbours for each vertex, and you may choose the starting vertex. Find the lexicographically minimal order that you can obtain.

The first line contains one integer $T$ ($1 \le T \le 10^{5}$), the number of test cases. Each test case begins with a line containing a single integer $n$ ($2 \le n \le 2 \cdot 10^{5}$), the number of vertices. The next $n-1$ lines each contain 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 between $u_i$ and $v_i$. The given graph is guaranteed to be a tree. The sum of $n$ over all test cases 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:

Starting from vertex 1, the only possible order is 2 3 1. Starting from vertex 2, the only possible order is 1 3 2. Starting from vertex 3, there are two possible 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:

Starting from vertex 1, there are two possible orders: 2 3 1 and 3 2 1. Starting from vertex 2, the only possible order is 3 1 2. Starting from vertex 3, the only possible order is 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, and it can be obtained by starting from vertex 7.