C. Trapmigiano Reggianotime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output 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). InputEach 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$$$. OutputFor 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.ExampleInput41 1 12 1 21 23 2 21 22 36 1 41 21 34 55 61 4Output1
1 2
3 1 2
1 4 3 2 6 5NoteIn 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}.$$$$$$