跟众生之门一样难欸！
首先这题要求的东西很鬼，距离异或和，看起来毫无性质。
不过毫无性质也是有好处的，你发现你一共有 \((n-2)!\) 种排列方式，值却只在 \([0,n-1]\)，也就是说取到一个值的概率会非常大！这种难以刻画的东西，显然是很难卡的，也就是说满足随机性。考虑到小数据随机方差可能会比较大，且 \(n\) 很小时会使得测试组数变大，我们对于 \(n\le 10\) 的情况跑暴力，否则我们跑 \(20n\) 次随机排列，我们并不需要对整个排列随机，直接随机交换两项即可。使用 \(\mathcal{O}(1)\) 求祖先的 trick 可以轻松通过。
对于输出答案我们可以记录每一时刻交换了哪些位置，然后记录在哪一时刻取到最小值就行了。
代码：
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i (l); i <= (r); ++ i)
#define rrp(i, l, r) for (int i (r); i >= (l); -- i)
#define eb emplace_back
using namespace std;
#define pii pair <int, int>
#define inf 1000000001
#define ls (p << 1)
#define rs (ls | 1)
#define fi first
#define se second
constexpr int N = 5e4 + 5, M = 2e5 + 5;
typedef long long ll;
typedef unsigned long long ull;
inline ll rd () {ll x = 0, f = 1;char ch = getchar ();while (! isdigit (ch)) {if (ch == '-') f = -1;ch = getchar ();}while (isdigit (ch)) {x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar ();}return x * f;
}
int qpow (int x, int y, int p) {int ret (1);for (; y; y >>= 1, x = x * x % p) if (y & 1) ret = ret * x % p;return ret;
}
int n, s, t;
int p[N];
int x[N * 20], y[N * 20];
vector <int> e[N];
int f[N][16], dep[N], dfn[N], dfu[N], tot;
mt19937 rnd (114514);
void dfs (int u, int fa) {dfn[u] = ++ tot;dep[u] = dep[fa] + 1;for (auto v : e[u]) {if (v == fa) continue;dfs (v, u);}dfu[u] = tot;
}
int get (int x, int y) {return dep[x] < dep[y] ? x : y;
}
int LCA_dep (int x, int y) {if (dfn[x] >= dfn[y]) swap (x, y);if (dfu[x] >= dfn[y]) return dep[x];int k (__lg (dfn[y] - dfn[x] + 1));return dep[get (f[dfn[x]][k], f[dfn[y] - (1 << k) + 1][k])] - 1;
}
int dist (int x, int y) {if (! x || ! y) return 0;return dep[x] + dep[y] - 2 * LCA_dep (x, y);
}
int q[N];
int calc (int x) {return dist (p[x - 1], p[x]) ^ dist (p[x], p[x + 1]);
}
int C;
void solve () {n = rd (), s = rd (), t = rd ();rep (i, 1, n) e[i].clear ();rep (i, 2, n) {int u (rd ()), v (rd ());e[u].eb (v), e[v].eb (u);} tot = 0, dfs (1, 0);rep (i, 1, n) f[dfn[i]][0] = i;rep (j, 1, 15) {rep (i, 1, n - (1 << j) + 1) {f[i][j] = get (f[i][j - 1], f[i + (1 << j - 1)][j - 1]);}}int k = n * 20;rep (i, 1, n) p[i] = i;rep (i, 1, n) {if (p[i] == t) swap (p[i], p[n]);if (p[i] == s) swap (p[i], p[1]);}shuffle (p + 2, p + n, rnd);rep (i, 1, n) q[i] = p[i];int now (0), ans (n + 1), id (0);if (n <= 10) {sort (p + 2, p + n);do {now = 0;rep (i, 1, n - 1) now ^= dist (p[i], p[i + 1]);if (now < ans) memcpy (q, p, sizeof q), ans = now;if (ans <= 1) break;} while (next_permutation (p + 2, p + n));} else {rep (i, 1, n) now ^= dist (p[i], p[i + 1]);rep (t, 1, k) {int i (rnd () % (n - 2) + 2), j (rnd () % (n - 2) + 2);while (j == i) j = rnd () % (n - 2) + 2;x[t] = i, y[t] = j;now ^= calc (i) ^ calc (j);swap (p[i], p[j]);now ^= calc (i) ^ calc (j);if (now < ans) {ans = now, id = t;}if (ans <= 1) break;}}rep (t, 1, id) swap (q[x[t]], q[y[t]]);now = 0;rep (i, 1, n) printf ("%d ", q[i]), q[i] = p[i] = 0; puts ("");
}
int32_t main () {// freopen ("1.in", "r", stdin);// freopen ("1.out", "w", stdout);for (int T (rd ()); T; -- T) solve ();
}