For a given tree with $n$ vertices (where $n > 2$), numbered from $1$ to $n$, its Prüfer code is a uniquely determined sequence of numbers of length $n - 2$, which can be obtained using the following simple algorithm:

while the tree has more than two vertices: find the vertex of degree 1 with the smallest number add the number of its only neighbor to the code remove the vertex from the tree

It can be proven that every sequence of length $n - 2$ consisting of numbers between $1$ and $n$ is a Prüfer code for some tree, and also that the Prüfer code uniquely determines the tree from which it originates. These and other fascinating facts about Prüfer codes can be found on Wikipedia.

In this problem, we are given a tree and we will consider Prüfer codes generated by different ways of numbering the vertices of this tree. If $S$ is some numbering of the vertices (i.e., formally, an injective function from the set of vertices to the set $\{1, \dots, n\}$), then $K(S)$ denotes the Prüfer code of the tree with vertices numbered in this way.

Your task is to determine the lexicographically smallest Prüfer code for a given tree, i.e., a sequence such that it is equal to $K(S)$ for some vertex numbering $S$, and at the same time, for every other vertex numbering $S'$, we have either $K(S) = K(S')$, or at the first position where $K(S)$ and $K(S')$ differ, the number in $K(S)$ is smaller.

You must solve this problem for $t$ independent test cases.

Input

The first line of the input contains one integer $t$ ($1 \le t \le 1000$), representing the number of test cases to solve.

The description of a test case begins with a line containing one integer $n$ ($3 \le n \le 1000$), representing the number of vertices in the tree. The vertices in the tree are numbered with numbers from $1$ to $n$, although this numbering does not necessarily correspond to the lexicographically smallest Prüfer code.

The next $n - 1$ lines describe the edges of the tree. Each such line contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$), indicating that vertices $a_i$ and $b_i$ are connected by an edge.

The sum of $n$ over all test cases is no greater than $5000$.

Output

Output $t$ lines, one for each test case. In the $i$-th line, output a sequence of $n - 2$ numbers, which is the lexicographically smallest Prüfer code for the optimal vertex numbering of the tree from the $i$-th test case.

Examples

Input 1

2
5
1 2
2 3
3 4
3 5
16
8 1
9 1
10 1
11 2
12 2
2 3
13 4
4 3
14 5
15 5
5 3
3 1
1 6
6 7
7 16

Output 1

1 1 2
1 1 1 2 2 3 4 3 5 5 3 1 6 7

Note

In the first test case, an example vertex numbering giving the lexicographically smallest Prüfer code is $1 \to 5, 2 \to 2, 3 \to 1, 4 \to 4, 5 \to 3$.

For such a numbering, the algorithm for determining the Prüfer code will in the first step choose the vertex with the new number $3$ (and add $1$ to the code, which is the new number of its only neighbor). In the second step, the vertex with the new number $4$ (whose only neighbor is also $1$) will be chosen. In the third step (after removing vertices $3$ and $4$), vertex $1$ is already a leaf, and it will be chosen, and the number of its neighbor, which is $2$, will be added as the last element of the code.

In the second test case, it is optimal not to renumber the vertices at all; moreover, the order of edges in the input corresponds to the order of removing leaves in the algorithm determining the Prüfer code.