Normally, there would be a problem background here in the style of the problem setter from 2022 (which is usually quite long), but the setter was disgusted by the terrible hotel Wi-Fi while submitting homework one night, and their laptop broke, so they were unable to write such a background before the deadline.

Little Z has a tree with $n$ nodes, where the $i$-th edge connects nodes $u_i$ and $v_i$.

Little Z wants to find a permutation or a cyclic permutation such that the total number of edges traversed when visiting all nodes in the order of the permutation, starting from the first node, is exactly $k$.

Specifically, given $op\in\{1,2\}$, you need to find a permutation $p$ of order $n$ that satisfies the following conditions:

1. If $op=1$, you need to satisfy $\sum_{i=1}^{n-1}dis(p_i,p_{i+1})=k$.
2. If $op=2$, you need to satisfy $\sum_{i=1}^ndis(p_i,p_{(i\ \bmod\ n)+1})=k$.

Here, $dis(x,y)$ is the number of edges on the shortest path between nodes $x$ and $y$ in the tree.

Little Z knows nothing about OI, so he hopes you can find a solution, or tell him that no such solution exists. If there are multiple possible solutions, you may output any one that satisfies the conditions.

Little Z has $T$ such problems, and you need to answer each of them.

Input

The first line of the input file contains a non-negative integer $T$, representing the number of test cases. The test cases follow.

For each test case, the first line contains three positive integers $n, k, op$, representing the number of nodes in the tree, the total distance required by Little Z, and the query type.

The next $n-1$ lines each contain two positive integers $u_i, v_i$, representing the edges of the tree.

Output

For each test case, output one line:

If no permutation satisfies the requirements for this test case, output $-1$.

Otherwise, output $n$ integers $p_1, \dots, p_n$ on this line, representing the permutation you found.

Examples

Examples 1

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

Output 1

3 4 2 1 5
-1
1

For the first test case, we can see that $dis(3,4)=3, dis(4,2)=1, dis(2,1)=1, dis(1,5)=2$, so it satisfies Little Z's requirement for the permutation.

For the second test case, it can be proven that no solution exists.

For the third test case, it is obvious that the only possible arrangement satisfies the condition.

Examples 2

3
5 10 2
1 2
1 3
2 4
2 5
4 6 2
1 2
1 3
1 4
1 0 2

Output 2

3 4 2 1 5
1 2 3 4
1

The situation for this set of examples is similar to the previous one, with the only difference being $op=2$, so when calculating the distance, we must additionally calculate $dis(p_1, p_n)$.

Constraints

For all data, it is guaranteed that $T\leq 5\times 10^5, 1\leq n\leq 5\times 10^5, \sum n\leq 5\times 10^5, 0\leq k\leq n^2, op\in\{1,2\}, 1\leq u_i, v_i\leq n$, and the given edges form a valid tree.

In a subtask, if you correctly answer all $op=1$ queries or all $op=2$ queries, but not all queries, you can receive $50\%$ of the score.

Note: If you only want to receive points for the $op=1$ or $op=2$ parts, you must still output content that follows the format for the remaining data. Any formatting error in any test case may result in $0$ points for the entire subtask.