背景

原题面存档。

题目描述

给定 $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)$ 构成一棵树。

特殊性质 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$ 个点的有标号树中等概率随机生成。