B. Permutation Tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree $$$T$$$ with $$$n$$$ vertices. Edge $$$i$$$ $$$(1 \le i \le n-1)$$$ connects vertices $$$u_i$$$ and $$$v_i$$$, $$$T$$$ is rooted at $$$x$$$ $$$(1 \le x \le n)$$$

You have to construct the lexicographically smallest $$$n$$$-permutation $$$p$$$ such that the following condition holds:

  • If $$$u$$$ is an ancestor to $$$v$$$, $$$p_u \lt p_v$$$.

Note: Ancestors of the vertex $$$u$$$ are all vertices on the path from the root $$$x$$$ to the vertex $$$u$$$ , except the vertex $$$u$$$ itself.

Input

The first line contains integers $$$n$$$ and $$$x$$$ $$$(2 \le n \le 2 \cdot 10^5)$$$ — the number of vertices in the tree and the root.

The next $$$n-1$$$ lines contain integers $$$u_i$$$ and $$$v_i$$$ $$$(1 \le v_i, u_i \le n)$$$ — the vertices that the $$$i$$$-th edge connects.

It is guaranteed that this set of edges forms a tree.

Output

The lexicographically smallest $$$n$$$-permutation that satisfies the given condition

Examples
Input
5 3
3 5
1 5
1 2
4 1
Output
3 4 1 5 2
Input
10 3
5 4
8 3
4 6
5 3
7 9
1 3
5 10
2 9
9 8
Output
2 5 1 7 6 8 9 3 4 10
Note

For the first example:

For the second example: