You are given a tree with $n$ nodes, connected by $n-1$ branches. There is a pigeon on each node.

You need to assign a number to each pigeon. Let $p_i$ be the number assigned to the pigeon on node $i$. You must satisfy the following conditions:

• The sequence $p$ is a permutation of $1 \sim n$, meaning each number from $1$ to $n$ appears exactly once among the pigeons' numbers.
• For any two nodes $u$ and $v$, if there is a branch between node $u$ and node $v$, the sum of the numbers assigned to the pigeons on these nodes must not exceed $n+1$, i.e., $p_u+p_v \le n+1$.

You are asked to find a valid assignment. It can be proven that at least one solution always exists.

Input

This problem contains multiple test cases.

The first line contains a positive integer $T$, representing the number of test cases.

Each test case is described as follows: - The first line contains a positive integer $n$. - The next $n-1$ lines each contain two positive integers $u_i, v_i$, indicating that there is a branch between node $u_i$ and node $v_i$.

Output

For each test case, output a single line containing $n$ positive integers, where the $i$-th integer represents the value $p_i$ assigned to the pigeon on node $i$.

It can be proven that at least one solution always exists.

Any output that satisfies the requirements will be accepted.

Examples

Input 1

2
3
1 2
1 3
5
4 2
1 5
3 1
2 1

Output 1

1 3 2
1 2 3 4 5

Note 1

For the first test case, the pigeon on node $1$ is assigned $1$, the pigeon on node $2$ is assigned $3$, and the pigeon on node $3$ is assigned $2$. Since $1+2 \le 4$ and $1+3 \le 4$, this assignment satisfies the conditions.

For the second test case, another valid assignment is to assign the numbers $2, 1, 4, 5, 3$ to the pigeons on nodes $1, 2, 3, 4, 5$ respectively.

Constraints

For all test cases, it is guaranteed that:

• $1 \le T \le 10$
• $2 \le n \le 10^5$
• $1 \le u_i, v_i \le n$
• The input data forms a tree.

This problem uses bundled testing.

• Subtask 1 (21 points): $n \le 8$.
• Subtask 2 (25 points): $n \le 1000$.
• Subtask 3 (11 points): For any positive integer $i < n$, $u_i=1$ and $v_i=i+1$.
• Subtask 4 (18 points): For any positive integer $i < n$, $u_i=i$ and $v_i=i+1$.
• Subtask 5 (25 points): No additional constraints.