#P18519. Tree and Permutation
Tree and Permutation
Tree and Permutation
给定一棵有 个结点的无向树,以及树上两个不同的结点 。结点编号为 ,每条边的长度均为 1。记 为 之间的距离,即连接它们的简单路径的边数。
你需要找出 的一个排列 ,满足:
- ,;
- 令 ,使
尽可能小,其中 表示按位异或。
如果有多种最优排列,输出任意一种。
输入格式
本题有多组测试数据。第一行包含一个正整数 (),表示测试数据组数。
对于每组测试数据,第一行包含三个正整数 ,满足 , 且 。
接下来 行,每行包含两个正整数 ,满足 且 ,表示树上有一条连接 的无向边。
保证输入描述一棵树,且所有测试数据的 之和不超过 。
输出格式
对于每组测试数据,输出一行 个正整数 。它们必须恰好构成 的一个排列,首项为 ,末项为 ,且相邻结点距离的异或和最小。
原题没有限制每一对相邻结点的距离。 距离可以大于 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