题目背景

为了完成师父留给小黑的最后一个任务，小黑一行人又进入了“众生之门”游戏中，而他们要完成这个师父给的最终任务的第一步便是快速获取经验升级……

题目描述

提示：我们在题目描述的最后提供了一份简要的、形式化描述的题面。

他们一开始并不希望通过击杀其他玩家升级，所以作为多年游戏玩家的山新帮助小黑找到了 $n$ 个拥有升级任务的地点，由 $1$ 到 $n$ 编号。这些地点由 $n - 1$ 条长度为 $1$ 的无向道路连接，使得任意两个地点都可以互相到达，换句话说这些地点与道路形成了一棵树。

小黑一行人决定确定一个任务完成顺序，也就是找到一个 $1$ 到 $n$ 的排列 $p_1,p_2,\cdots,p_n$，然后他们会先完成地点 $p_1$ 的任务，然后沿着 $p_1$ 到 $p_2$ 的简单路径走到 $p_2$ 并完成地点 $p_2$ 的任务，依次完成所有任务直到最后走到 $p_n$。

同时，他们给定了两个地点 $s, t$，他们希望能够最先完成 $s$ 地点的任务并且最后完成 $t$ 地点的任务，也就是 $p_1=s$ 且 $p_n=t$。

然而剧集播到这里就到最新话了，而你却迫不及待地想要知道后面的剧情，于是你决定自己找到一个较好的方案。

记 $d_i(1\leq i\leq n-1)$ 表示地点 $p_i$ 与地点 $p_{i+1}$ 的简单路径的长度，对于拥有多年算法竞赛经验的你来说，最小化 $\sum_{i = 1} ^ {n - 1}d_i$ 的方案太容易了。你决定多来一点挑战性，找到最小化 $\oplus_{i = 1} ^ {n - 1}d_i$ 的方案，这里的 $\oplus$ 表示的是按位异或。

形式化的：给定 $n$、一棵 $n$ 个点的无向树和树上的两个不相同的节点 $s,t$，其中每条边的长度均为 $1$。节点由 $1$ 至 $n$ 的整数编号。记 $\mathrm{dist}(u,v)$ 表示 $u$ 和 $v$ 的距离（即简单路径经过的边数）。你需要给出一个 $1$ 到 $n$ 的排列 $p_1,p_2,\cdots,p_n$ 满足以下两个条件：

• $p_1=s$，$p_n=t$；
• 设 $d_i=\mathrm{dist}(p_i,p_{i+1})(1\leq i\leq n-1)$，那么你给出的排列需要满足以上条件的前提下，最小化 $\oplus_{i = 1} ^ {n - 1}d_i$，其中 $\oplus$ 表示按位异或。

如果有多种满足条件的排列，输出任意一种均可。

输入格式

从标准输入读入数据。

本题有多组测试数据。第一行输入一个正整数 $T$ 表示测试数据组数。

对于每组数据，第一行输入三个正整数 $n,s,t$，接下来 $n-1$ 行每行两个正整数 $u,v$，表示地点 $u$ 和 $v$ 有直接无向道路连接（即树上的一条边）。

输出格式

输出到标准输出。

对于每组数据，输出一行 $n$ 个正整数 $p_1,p_2,\cdots,p_n$，你需要保证其为 $1$ 到 $n$ 的一个排列且 $p_1=s$，$p_n=t$，且 $\oplus_{i = 1} ^ {n - 1} d_i$ 最小。

3
3 1 3
1 2
2 3
4 3 4
1 2
2 3
2 4
5 1 2
1 2
1 3
2 4
3 5

1 2 3
3 2 1 4
1 5 3 4 2

见题目目录下的 2.in 与 2.ans。

提示

样例 1 解释

该样例共有三组测试数据。

• 对于第一组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $0$，样例输出为 $1,2,3$，其中 $d_1=d_2=1$。
• 对于第二组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $2$，样例输出为 $3,2,1,4$，其中 $d_1=d_2=1$，$d_3=2$；另一种合法输出为 $3,1,2,4$。
• 对于第三组数据，$\oplus_{i = 1} ^ {n - 1} d_i$ 最小可以取到 $1$，样例输出为 $1,5,3,4,2$，其中 $d_1=2$，$d_2=1$，$d_3=3$，$d_4=1$。

样例 2 解释

值得注意的是，该输入数据由所有满足 $n\leq 10$ 的，且所有不同 $s$ 和 $t$ 的相对位置的可能的树形态构成。

这个样例，无疑是善良的出题人无私的馈赠。中间忘了。出题人相信，这个美妙的样例，可以给拼搏于 AC 这道题的逐梦之路上的你，提供一个有力的援助。

数据范围

设 $\sum n$ 表示单个测试点内所有数据的 $n$ 的和。对于所有测试数据，

• $T≥1$；
• $2\leq n\leq 5\times 10 ^4$，$\sum n\leq 5\times 10 ^ 5$；
• $1\leq s,t\leq n$，$s\neq t$；
• $1\le u,v\le n$，$u\neq v$；
• 输入的 $n-1$ 个 $(u,v)$ 构成一棵树。

子任务编号	$n$	$\sum n$	特殊性质	分数
1	$\le 8$	$\le 10^{3}$	无	5
2	$\le 12$			8
3	$\le 5 \times 10^{4}$	$\le 5 \times 10^{5}$	A	17
4			B	20
5			C	17
6	$\le 10^{3}$	$\le 10^{4}$	D	10
7	$\le 5 \times 10^{4}$	$\le 5 \times 10^{5}$	无	23

特殊性质 A：保证每个点度数小于等于 $2$。

特殊性质 B：保证对于任意 $x$ 有 $\mathrm{dist}(s,x)+\mathrm{dist}(x,t)\le \mathrm{dist}(s,t)+2$。

特殊性质 C：保证 $\mathrm{dist}(s,t)=1$。

特殊性质 D：该子任务共有五个测试点，对于每一个测试点，保证 $T=10$ 且 $n=1000$，并且每个测试数据中，$s$ 在 $1\sim n$ 中等概率随机生成，$t$ 从 $1\sim n$ 除去 $s$ 中等概率随机生成，树从所有 $n$ 个点的有标号树中等概率随机生成。