Problem Description

A tree is a type of structure called a "graph" consisting of vertices and edges. With $N$ vertices, there are $N-1$ edges, and every vertex is connected indirectly or directly to all other vertices.

In this problem, there are $N$ vertices numbered from 1 to $N$.

Given a tree, output the lexicographically smallest sequence that can be formed by the following operations:

1. Start by selecting vertex 1.
2. Repeatedly select one of the vertices that is connected by an edge to any of the previously selected vertices and has not been selected yet, until there are no more unselected vertices.
3. Form a sequence by arranging the vertex numbers in the order they were selected.

For two sequences of length $N$, $A=\{a_1,a_2,\ ...,a_N\}$ and $B=\{b_1,b_2,\ ...,b_N\}$, $A$ is lexicographically smaller than $B$ if there exists a $k(1≦k≦N)$ such that:

• $a_i = b_i$ for $i < k$
• $a_k < b_k$

Input Format

The input is given from the standard input in the following format:

$N$ $a_1$ $b_1$ $a_2$ $b_2$ : $a_{N-1}$ $b_{N-1}$

• The first line contains an integer $N\ (2 ≦ N ≦ 10^5)$, representing the number of vertices in the tree.
• The next $N-1$ lines contain the edge information of the tree. The $i$-th line $(1 ≦ i ≦ N-1)$ contains two integers $a_i$ and $b_i$, indicating an edge between vertex $a_i$ and vertex $b_i$.
• It is guaranteed that the $N$ vertices connected by $N-1$ edges form a tree.

Output Format

Output one line containing the lexicographically smallest sequence formed from the given tree, separated by spaces.

Do not forget the newline at the end of the line. Also, do not include any extra spaces at the end of the line.

Sample Input and Output

Sample Input #1

4
1 3
1 4
2 3

Sample Output #1

1 3 2 4

Sample Input #2

6
1 2
2 3
2 6
6 4
1 5

Sample Output #2

1 2 3 5 6 4

Sample Input #3

7
1 5
5 2
5 3
5 7
5 6
6 4

Sample Output #3

1 5 2 3 6 4 7

Notes/Hints

Partial Points

This problem has partial points:

• For 50 points, $1 ≦ N ≦ 3,000$.

Sample Explanation 1

This is the tree from the problem statement. First, select vertex $1$. Next, select vertex $3$. Note that vertex $2$ cannot be selected because it is not connected to any previously selected vertices (only vertex $1$ in this case). Then, select vertex $2$. Finally, select vertex $4$. Arranging the vertex numbers in the order they were selected gives the sequence $1 3 2 4$, which is the lexicographically smallest possible sequence.

见题面 Input 部分

见题面 Output 部分