Problem Description

Xiao Y is an OIer who loves traveling. She arrives in Country X, planning to visit all the cities.

Xiao Y learns that there are $n$ cities in Country X connected by $m$ bidirectional roads. Each road connects two cities. There are no two roads connecting the same pair of cities, nor any road connecting a city to itself. Moreover, from any city, one can reach any other city through these roads. Xiao Y can only travel between cities using these roads.

Xiao Y's travel plan is as follows: she starts from any city and, from the starting point, can choose a road connected to the current city to go to a city she hasn't visited yet, or return to the previous city along the road she first used to visit the current city. When Xiao Y returns to the starting point, she can choose to end her trip or continue traveling. It is important to note that Xiao Y requires every city to be visited during her travel plan.

To make her travel more meaningful, Xiao Y decides to record the number of each new city she visits (including the starting point). She knows this will form a sequence of length $n$. She hopes this sequence will have the smallest lexicographical order. Can you help her?

For two sequences $A$ and $B$ of the same length $n$, the sequence $A$ is lexicographically smaller than $B$ if and only if there exists a positive integer $x$ such that:

• For any positive integer $1 ≤ i < x$, the $i$-th element of sequence $A$ ($A_i$) is the same as the $i$-th element of sequence $B$ ($B_i$).
• The $x$-th element of sequence $A$ is smaller than the $x$-th element of sequence $B$.

Input Format

The input file consists of $m + 1$ lines. The first line contains two integers $n, m (m ≤ n)$, separated by a space.

The next $m$ lines each contain two integers $u, v (1 ≤ u, v ≤ n)$, indicating that there is a road between cities numbered $u$ and $v$, separated by a space.

Output Format

The output file contains one line with $n$ integers, representing the lexicographically smallest sequence. Adjacent integers are separated by a space.

Sample Input and Output

Input Sample #1

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

Output Sample #1

1 3 2 5 4 6

Input Sample #2

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

Output Sample #2

1 3 2 4 5 6

Notes

For $100\%$ of the data and all samples, $1 \le n \le 500000$ and $m = n - 1$ or $m = n$.

Detailed specifications can be found in the normal version (excluding test cases 11-13).

见题面 Input 部分

见题面 Output 部分