Problem Description

Xiao Y is an OIer who loves traveling. She came to Country X and plans to visit all the cities.

Xiao Y learned that there are $n$ cities in Country X with $m$ two-way roads between them. Each two-way road connects two cities. There are no two roads connecting the same pair of cities, and there is no road connecting a city to itself. Also, starting from any city, one can reach any other city through these roads. Xiao Y can only travel from one city to another using these roads.

Xiao Y's travel plan is as follows: she can choose any city as the starting point, and then starting from the starting point, each time she can choose a road connected to the current city to go to a city she has not visited yet, or she can go back to the previous city along the road she used when she first visited the current city. When Xiao Y returns to the starting point, she may choose to end the trip or continue traveling. Note that Xiao Y requires that in the travel plan, every city must be visited.

To make her trip more meaningful, Xiao Y decides that each time she arrives at a new city (including the starting point), she will record its index. She knows this will form a sequence of length $n$. She wants this sequence to be lexicographically smallest. Can you help her?

For two sequences $A$ and $B$ of length $n$, we say that $A$ is lexicographically smaller than $B$ if and only if there exists a positive integer $x$ such that the following conditions hold:

• For any positive integer $1 \le i < x$, the $i$-th element $A_i$ of $A$ is equal to the $i$-th element $B_i$ of $B$.
• The value of the $x$-th element of $A$ is less than the value of the $x$-th element of $B$.

Input Format

The input file contains a total of $m + 1$ lines. The first line contains two integers $n, m (m \le n)$, separated by a single space.

The next $m$ lines each contain two integers $u, v (1 \le u, v \le n)$, indicating that there is a road between the cities indexed $u$ and $v$. The two integers are separated by a single space.

Output Format

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

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

1 3 2 5 4 6

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

1 3 2 4 5 6

Hint

Constraints.

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

For detailed specifications, see the normal version (excluding testcase11-13).

Translated by ChatGPT 5