给定一个整数 $n$，一棵包含 $n$ 个节点的无向树，以及树上两个不同的节点 $s$ 和 $t$，其中每条边的长度均为 $1$。节点编号为 $1$ 到 $n$。令 $dist(u, v)$ 表示节点 $u$ 和 $v$ 之间的距离（即它们之间简单路径上的边数）。你需要找到一个 $1$ 到 $n$ 的排列 $p_1, p_2, \dots, p_n$，满足以下两个条件：

• $p_1 = s, p_n = t$；
• 对于 $d_i = dist(p_i, p_{i+1})$（其中 $1 \le i \le n - 1$），该排列应使 $\bigoplus_{i=1}^{n-1} d_i$ 最小化，其中 $\oplus$ 表示按位异或运算。

如果存在多个满足条件的排列，输出其中任意一个即可。

输入格式

本题包含多个测试点。第一行输入一个正整数 $T$ ($T \ge 1$)，表示测试点数量。

对于每个测试点，第一行输入三个正整数 $n, s, t$ ($2 \le n \le 5 \times 10^4, 1 \le s, t \le n, s \neq t$)。 接下来的 $n - 1$ 行，每行包含两个正整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示位置 $u$ 和 $v$ 之间有一条直接的无向道路连接（即树上的一条边）。

保证所有测试点的 $n$ 之和不超过 $5 \times 10^5$。

输出格式

对于每个测试点，输出一行包含 $n$ 个正整数 $p_1, p_2, \dots, p_n$，确保它是 $1$ 到 $n$ 的一个排列，满足 $p_1 = s, p_n = t$，且 $\bigoplus_{i=1}^{n-1} d_i$ 最小化。

样例

样例输入 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

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

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