Problem Background

To complete the final task left by his master, Xiao Hei and his companions have entered the "Gate of All Living Beings" game. The first step to completing this final task is to quickly gain experience and level up...

Description

Note: We provide a brief, formal description of the problem at the end of the problem statement.

Initially, they do not wish to level up by killing other players. Therefore, Shan Xin, a veteran gamer, helped Xiao Hei find $n$ locations with leveling tasks, numbered from $1$ to $n$. These locations are connected by $n-1$ undirected roads of length $1$, such that any two locations can reach each other. In other words, these locations and roads form a tree.

Xiao Hei and his companions decide to determine a task completion order, which is a permutation $p_1, p_2, \dots, p_n$ of $1$ to $n$. They will complete the task at location $p_1$ first, then travel along the simple path from $p_1$ to $p_2$ to reach $p_2$ and complete the task there, and so on, until they finally reach $p_n$ and complete the last task.

At the same time, they are given two locations $s$ and $t$. They wish to complete the task at location $s$ first and the task at location $t$ last, meaning $p_1=s$ and $p_n=t$.

However, the series has reached its latest episode, and you are eager to know what happens next. Thus, you decide to find a better plan yourself.

Let $d_i (1 \le i \le n-1)$ denote the length of the simple path between location $p_i$ and location $p_{i+1}$. For someone with years of experience in algorithmic competitions, minimizing $\sum_{i=1}^{n-1}d_i$ is too easy. You decide to add more challenge by finding a plan that minimizes $\oplus_{i=1}^{n-1}d_i$, where $\oplus$ denotes the bitwise XOR operation.

Formally: Given $n$, an undirected tree with $n$ nodes, and two distinct nodes $s, t$ on the tree, where each edge has a length of $1$. Nodes are numbered 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 provide a permutation $p_1, p_2, \dots, 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 \le i \le n-1)$. Under the premise of satisfying the above conditions, minimize $\oplus_{i=1}^{n-1} d_i$, where $\oplus$ denotes bitwise XOR.

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

Input

Read data from standard input.

This problem contains multiple test cases. The first line contains a positive integer $T$ representing 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

Output to standard output.

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

Examples

Example 1 Input

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

Example 1 Output

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

Note

This example contains three test cases.

• For the first test case, the minimum 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 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, d_3=2$; another valid output is $3, 1, 2, 4$.
• For the third test case, the minimum 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$.

Examples

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

Note

It is worth noting that this input data consists of all possible tree structures for $n \le 10$ and all possible relative positions of $s$ and $t$.

This example is undoubtedly a selfless gift from the kind problem setter. (Content omitted). The problem setter believes that this wonderful example can provide powerful assistance to you as you strive to AC this problem.

Subtasks

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

• $T \ge 1$;
• $2\le n\le 5\times 10^4$, $\sum n\le 5\times 10^5$;
• $1\le s,t \le n$, $s\ne t$;
• $1 \le u, v \le n$, $u \ne v$;
• The $n-1$ input $(u, v)$ pairs form a tree.

Special Property A: The degree of every node is guaranteed to be at most $2$.

Special Property B: For any $x$, it is guaranteed that $\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 contains five test cases. For each test case, it is guaranteed that $T=10$ and $n=1000$. In each test case, $s$ is chosen uniformly at random from $1 \sim n$, $t$ is chosen uniformly at random from $1 \sim n$ excluding $s$, and the tree is chosen uniformly at random from all labeled trees with $n$ nodes.