CF2071C.Trapmigiano Reggiano

在一个意大利村庄中，一只饥饿的老鼠从给定树 $^{\text{∗}}$ 的顶点 $\textrm{st}$ 出发，该树包含 $n$ 个顶点。

给定一个长度为 $n$ 的排列 $p$ $^{\text{†}}$，共有 $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}$。

若存在多个解，输出任意一个即可。

第一个测试用例中，当 $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{en}.$$

翻译由 DeepSeek R1 完成