← 返回题目列表

Codeforces · 2071/C

C. 特拉米吉亚诺·雷吉亚诺

中文机器翻译题面 查看原题

在意大利的一个村庄里,一只饥饿的老鼠从给定树 $$$^{\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}$$$ 处被捕获。

如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

4
1 1 1
2 1 2
1 2
3 2 2
1 2
2 3
6 1 4
1 2
1 3
4 5
5 6
1 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}.$$