#P18519. Tree and Permutation

Tree and Permutation

Tree and Permutation

给定一棵有 nn 个结点的无向树,以及树上两个不同的结点 s,ts,t。结点编号为 1,2,…,n1,2,\ldots,n,每条边的长度均为 1。记 dist⁡(u,v)\operatorname{dist}(u,v) 为 u,vu,v 之间的距离,即连接它们的简单路径的边数。

你需要找出 1,2,…,n1,2,\ldots,n 的一个排列 p1,p2,…,pnp_1,p_2,\ldots,p_n,满足:

  • p1=sp_1=s,pn=tp_n=t;
  • 令 di=dist⁡(pi,pi+1)d_i=\operatorname{dist}(p_i,p_{i+1}),使
$$d_1\mathbin\oplus d_2\mathbin\oplus\cdots\mathbin\oplus d_{n-1}$$

尽可能小,其中 ⊕\oplus 表示按位异或。

如果有多种最优排列,输出任意一种。

输入格式

本题有多组测试数据。第一行包含一个正整数 TT(T≥1T\ge1),表示测试数据组数。

对于每组测试数据,第一行包含三个正整数 n,s,tn,s,t,满足 2≤n≤5×1042\le n\le5\times10^4,1≤s,t≤n1\le s,t\le n 且 s≠ts\ne t。

接下来 n−1n-1 行,每行包含两个正整数 u,vu,v,满足 1≤u,v≤n1\le u,v\le n 且 u≠vu\ne v,表示树上有一条连接 u,vu,v 的无向边。

保证输入描述一棵树,且所有测试数据的 nn 之和不超过 5×1055\times10^5。

输出格式

对于每组测试数据,输出一行 nn 个正整数 p1,…,pnp_1,\ldots,p_n。它们必须恰好构成 1,…,n1,\ldots,n 的一个排列,首项为 ss,末项为 tt,且相邻结点距离的异或和最小。

原题没有限制每一对相邻结点的距离。 距离可以大于 3,只要求最终异或和达到全局最小值。

原样例 1

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

3
10 2 3
7 5
6 1
9 1
4 5
3 10
5 1
10 9
1 2
8 3
10 3 7
5 6
4 8
9 1
6 3
7 3
2 5
10 1
8 9
1 6
10 10 4
5 10
1 4
4 5
6 1
9 6
2 10
8 1
3 6
7 4
2 6 5 4 7 1 9 8 10 3
3 5 2 1 4 8 9 10 6 7
10 2 5 7 1 8 6 3 9 4