In an Italian village, a hungry mouse starts at vertex $\textrm{st}$ on a given tree$^{\text{∗}}$ with $n$ vertices.

Given a permutation $p$ of length $n$$^{\text{†}}$, there are $n$ steps. For the $i$-th step:

• A tempting piece of Parmesan cheese appears at vertex $p_i$. If the mouse is currently at vertex $p_i$, it will stay there and enjoy the moment. Otherwise, it will move along the simple path to vertex $p_i$ by one edge.

Your task is to find such a permutation so that, after all $n$ steps, the mouse inevitably arrives at vertex $\textrm{en}$, where a trap awaits.

Note that the mouse must arrive at $\textrm{en}$ after all $n$ steps, though it may pass through $\textrm{en}$ earlier during the process.

$^{\text{∗}}$A tree is a connected graph without cycles. $^{\text{†}}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $\textrm{st}$, and $\textrm{en}$ ($1 \le n \le 10^5$; $1 \le \textrm{st}, \textrm{en} \le n$) — the number of vertices of the tree, the starting vertex, and the trap vertex.

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$, $u \neq v$) — the indices of the vertices connected by an edge.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

Output

For each test case:

• If no such permutation exists, output $-1$.
• Otherwise, output $n$ integers $p_1, p_2, \ldots, p_n$, representing the order in which the cheese will appear at the vertices, ensuring the mouse will eventually be caught at vertex $\textrm{en}$.

If there are multiple solutions, print any of them.

Note

In the first test case, there is only one permutation with length $n = 1$ that is $p = [1]$, which successfully catches the mouse:

$$\textrm{st} = 1 \overset{p_1 = 1}{\xrightarrow{\hspace{1.3cm}}} 1 = \textrm{en}.$$

In the second test case, one possible permutation with length $n = 2$ is $p = [1, 2]$:

$$\textrm{st} = 1 \overset{p_1 = 1}{\xrightarrow{\hspace{1.3cm}}} 1 \overset{p_2 = 2}{\xrightarrow{\hspace{1.3cm}}} 2 = \textrm{en}.$$

In the third test case, one possible permutation with length $n = 3$ is $p = [3, 1, 2]$:

$$\textrm{st} = 2 \overset{p_1 = 3}{\xrightarrow{\hspace{1.3cm}}} 3 \overset{p_2 = 1}{\xrightarrow{\hspace{1.3cm}}} 2 \overset{p_3 = 2}{\xrightarrow{\hspace{1.3cm}}} 2 = \textrm{en}.$$$$$$