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}.$$$$$$

Trapmigiano Reggiano

Examples