Minimize XOR of Distances on Tree Path Permutations

You are given an undirected tree with n nodes numbered from 1 to n and two distinct nodes s and t. Each edge of the tree has length 1. Let \( \mathrm{dist}(u,v) \) denote the number of edges on the unique simple path between nodes \( u \) and \( v \) in the tree.

Your task is to output a permutation \( p_1, p_2, \dots, p_n \) of the numbers from 1 to \( n \) such that:

• \( p_1 = s \) and \( p_n = t \);
• If we define \( d_i = \mathrm{dist}(p_i, p_{i+1}) \) for \( 1 \le i \le n-1 \), then the permutation minimizes \( \bigoplus_{i=1}^{n-1} d_i \), where \( \oplus \) is the bitwise XOR operator.

If there are multiple valid answers, output any one of them.

Note: In the input, s and t are given, and you are not allowed to visit t until the very end of the permutation (i.e. as the last element).

inputFormat

The first line contains three integers n s t (the number of nodes, the start node and the end node).

Each of the following \( n-1 \) lines contains two integers u v representing an undirected edge of the tree.

outputFormat

Output a permutation of \( \{1,2,...,n\} \) in one line (separated by spaces) that starts with s, ends with t and minimizes \( \bigoplus_{i=1}^{n-1} \mathrm{dist}(p_i,p_{i+1}) \) over all such permutations.

sample

3 1 3
1 2
2 3

1 2 3