在意大利的一个村庄里,一只饥饿的老鼠从给定树 $$$^{\text{*}}$$$ 的顶点 $$$\textrm{st}$$$ 开始,有 $$$n$$$ 个顶点。
给定长度为 $$$n$$$$$$^{\text{†}}$$$ 的排列 $$$p$$$,有 $$$n$$$ 个步骤。对于第 $$$i$$$ 步骤:
- 一块诱人的帕尔马干酪出现在顶点 $$$p_i$$$ 处。如果鼠标当前位于顶点 $$$p_i$$$,它将停留在那里并享受这一刻。否则,它将沿着简单路径移动到顶点$$$p_i$$$ 通过一个边缘.
你的任务是找到这样的排列,以便在完成所有$$$n$$$步骤后,鼠标不可避免地到达顶点$$$\textrm{en}$$$,那里有一个陷阱等待着。
请注意,鼠标必须在所有 $$$n$$$ 步骤后到达 $$$\textrm{en}$$$,尽管它可能在此过程中更早地穿过 $$$\textrm{en}$$$。
$$$^{\text{*}}$$$树是没有环的连通图。
$$$^{\text{†}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$\textrm{st}$$$ 和 $$$\textrm{en}$$$ ($$$1 \le n \le 10^5$$$; $$$1 \le \textrm{st}, \textrm{en} \le n$$$) — 树的顶点数,起始点顶点和陷阱顶点。
接下来的 $$$n - 1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) — 由边连接的顶点的索引。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。
输出
对于每个测试用例:
- 如果不存在这样的排列,则输出$$$-1$$$。
- 否则,输出 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$,表示奶酪出现在顶点的顺序,确保鼠标最终会在顶点 $$$\textrm{en}$$$ 处被捕获。
如果有多个解决方案,请打印其中任何一个。
示例
输入复制
41 1 12 1 21 23 2 21 22 36 1 41 21 34 55 61 4
输出复制
1 1 2 3 1 2 1 4 3 2 6 5
注意
在第一个测试用例中,只有一个长度 $$$n = 1$$$ 的排列,即 $$$p = [1]$$$,它成功捕获了鼠标:
$$\textrm{st} = 1 \overset{p_1 = 1}{\xrightarrow{\hspace{1.3cm}}} 1 = \textrm{en}.$$
在第二个测试用例中,长度 $$$n = 2$$$ 的一种可能排列是 $$$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}.$$
在第三个测试用例中,长度 $$$n = 3$$$ 的一种可能排列是 $$$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{zh}.$$