Problem Description

Given \( n \), an undirected tree with \( n \) nodes, and two distinct nodes \( s \) and \( t \) on the tree, where each edge has a length of 1. The nodes are numbered from 1 to \( n \). Let \( \mathrm{dist}(u, v) \) denote the distance between nodes \( u \) and \( v \) (i.e., the number of edges in the simple path between them). You need to provide a permutation \( p_1, p_2, \cdots, p_n \) of the numbers from 1 to \( n \) that satisfies the following conditions:

• \( p_1 = s \) and \( p_n = t \);
• Let \( d_i = \mathrm{dist}(p_i, p_{i+1}) \) for \( 1 \leq i \leq n-1 \). The permutation you provide must minimize \( \oplus_{i = 1}^{n-1} d_i \), where \( \oplus \) denotes the bitwise XOR operation.

If there are multiple permutations that satisfy the conditions, output any one of them.

Input Format

Input is read from the standard input.

This problem contains multiple test cases. The first line of input 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 locations \( u \) and \( v \) (i.e., an edge in the tree).

Output Format

Output is written to the standard output.

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

Sample Input and Output

Sample Input #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

Sample Output #1

1 2 3
3 2 1 4
1 5 3 4 2

Sample Input #2

See the files 2.in and 2.ans in the problem directory.

Sample Output #2

Notes

Sample 1 Explanation

This sample contains three test cases.

• For the first case, the minimum possible value of \( \oplus_{i = 1}^{n-1} d_i \) is 0, and the sample output is \( 1, 2, 3 \), where \( d_1 = d_2 = 1 \).
• For the second case, the minimum possible value of \( \oplus_{i = 1}^{n-1} d_i \) is 2, and 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 case, the minimum possible value of \( \oplus_{i = 1}^{n-1} d_i \) is 1, and the sample output is \( 1, 5, 3, 4, 2 \), where \( d_1 = 2 \), \( d_2 = 1 \), \( d_3 = 3 \), and \( d_4 = 1 \).

Sample 2 Explanation

Note that this input data consists of all possible tree shapes with \( n \leq 10 \) and all different relative positions of \( s \) and \( t \).

This sample is undoubtedly a generous gift from the kind problem setter. The problem setter believes that this wonderful sample can provide strong assistance to those striving to AC this problem.

Data Range

Let \( \sum n \) denote the sum of \( n \) across all data in a single test point. For all test data,

• \( T \geq 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 \leq u, v \leq n \), \( u \neq v \);
• The \( n-1 \) pairs \( (u, v) \) form a tree.

Special Condition A: Each node has a degree of at most 2.

Special Condition B: For any \( x \), \( \mathrm{dist}(s, x) + \mathrm{dist}(x, t) \leq \mathrm{dist}(s, t) + 2 \).

Special Condition C: \( \mathrm{dist}(s, t) = 1 \).

Special Condition D: This subtask contains five test points. For each test point, \( T = 10 \) and \( n = 1000 \). In each test case, \( s \) is randomly generated with equal probability from \( 1 \sim n \), and \( t \) is randomly generated with equal probability from \( 1 \sim n \) excluding \( s \). The tree is randomly generated with equal probability from all labeled trees with \( n \) nodes.

见题面 Input 部分

见题面 Output 部分