P5049 [NOIP 2018 Senior] Travel Enhanced Version.

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$.

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.

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

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