Background

Original statement archive.

Problem Description

Given $n$, an undirected tree with $n$ nodes, and two different nodes $s,t$ on the tree. Each edge has length $1$. Nodes are labeled with integers from $1$ to $n$. Let $\mathrm{dist}(u,v)$ denote the distance between $u$ and $v$ (i.e., the number of edges on the simple path). You need to output a permutation $p_1,p_2,\cdots,p_n$ of $1$ to $n$ that satisfies the following two conditions:

• $p_1=s$, $p_n=t$.
• Let $d_i=\mathrm{dist}(p_i,p_{i+1})(1\leq i\leq n-1)$. Under the above conditions, your permutation should minimize $\oplus_{i = 1} ^ {n - 1}d_i$, where $\oplus$ denotes bitwise XOR.

If there are multiple valid permutations, you may output any one of them.

Input Format

Read input from standard input.

This problem contains multiple test cases. The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains three positive integers $n,s,t$. The next $n-1$ lines each contain two positive integers $u,v$, indicating that there is a direct undirected road between $u$ and $v$ (i.e., an edge of the tree).

Output Format

Write output to standard output.

For each test case, output one line of $n$ positive integers $p_1,p_2,\cdots,p_n$. You must ensure it is a permutation of $1$ to $n$ with $p_1=s$ and $p_n=t$, and that $\oplus_{i = 1} ^ {n - 1} d_i$ is minimized.

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。

Hint

Sample 1 Explanation

This sample contains three test cases.

• For the first test case, the minimum possible value of $\oplus_{i = 1} ^ {n - 1} d_i$ is $0$. The sample output is $1,2,3$, where $d_1=d_2=1$.
• For the second test case, the minimum possible value of $\oplus_{i = 1} ^ {n - 1} d_i$ is $2$. The sample output is $3,2,1,4$, where $d_1=d_2=1$ and $d_3=2$; another valid output is $3,1,2,4$.
• For the third test case, the minimum possible value of $\oplus_{i = 1} ^ {n - 1} d_i$ is $1$. The sample output is $1,5,3,4,2$, where $d_1=2$, $d_2=1$, $d_3=3$, $d_4=1$.

Sample 2 Explanation

Note that this input consists of all tree shapes that satisfy $n\leq 10$ and all possible relative positions of different $s$ and $t$.

This sample is undoubtedly a selfless gift from the kind problem setter. I forgot what happened in the middle. The problem setter believes that this wonderful sample can provide strong help to you on your dream-chasing road of getting AC on this problem.

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases in a single test file. For all testdata,

• $T\ge 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$.
• The $n-1$ input pairs $(u,v)$ form a tree.

Special Property A: It is guaranteed that the degree of each node is at most $2$.

Special Property B: It is guaranteed that for any $x$, $\mathrm{dist}(s,x)+\mathrm{dist}(x,t)\le \mathrm{dist}(s,t)+2$.

Special Property C: It is guaranteed that $\mathrm{dist}(s,t)=1$.

Special Property D: This subtask has five test points. For each test point, it is guaranteed that $T=10$ and $n=1000$. In each test case, $s$ is generated uniformly at random from $1\sim n$, $t$ is generated uniformly at random from $1\sim n$ excluding $s$, and the tree is generated uniformly at random from all labeled trees on $n$ nodes.

Translated by ChatGPT 5