- Time limit: 1.00 s
- Memory limit: 512 MB
Your task is to find an order of the vertices where the distance between adjacent vertices is at most $3$.
Input
The first line of input consists of an integer $t$: the number of test cases.
After that, the first line of each test contains the number of nodes $n$. The following $n-1$ lines describe the edges of the tree.
Output
For each test print $n$ numbers: the order of the vertices. You may print any valid solution.
Example
Input:
2
4
1 2
1 3
1 4
3
1 2
2 3
Output:
1 2 3 4
2 1 3
Subtask 1 (29 points)
- $1 \le t \le 100$
- $1 \le n \le 8$
- $1 \le t \le 100$
- $1 \le n \le 100$