Travel

Problem Source

NOIP 2018 Senior Division

Problem Description

Little Y is an OIer who loves travelling. She comes to country X, planning to visit every city.

Little Y learns that the $n$ cities of X are connected by $m$ two-way roads. Each two-way road connects two cities. There are no two roads connecting the same pair of cities, and no road connecting a city to itself. Moreover, starting from any city, you can reach any other city through these roads. Little Y can only travel from one city to another along these roads.

Little Y's travel plan is as follows: freely choose any city as the starting point, then from the start, each time she may choose a road connected to the current city and go to a city she has not yet visited, or follow the road she used the first time she arrived at the current city and step back to the previous city. When Little Y returns to the starting point, she may choose to end the trip or continue. Note that Little Y requires every city to be visited in the travel plan.

To make her trip more meaningful, Little Y decides to record the number of each new city (including the start) the moment she arrives at it. 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$, both of length $n$, we say $A$ is lexicographically smaller than $B$ if and only if there exists a positive integer $x$ such that:

• For every positive integer $1 \leq i < x$, the $i$-th element $A_i$ of $A$ equals the $i$-th element $B_i$ of $B$.
• The $x$-th element of $A$ is strictly smaller than the $x$-th element of $B$.

Input Format

The input file has $m + 1$ lines in total. The first line contains two integers $n,m(1\leq n \leq 5000, n-1\leq m \leq n)$, separated by a single space.

The next $m$ lines each contain two integers $u,v (1 \leq u,v \leq n)$, indicating a road between cities $u$ and $v$, separated by a single space.

Output Format

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

Sample Input 1

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

Sample Output 1

1 3 2 5 4 6

Sample Input 2

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

Sample Output 2

1 3 2 4 5 6

Constraints

$1\leq n \leq 5000$, $n-1\leq m \leq n$.

Hint

• The graph is either a tree ($m = n-1$) or a tree plus exactly one extra edge ($m = n$). To obtain the lexicographically smallest sequence, always try to move to the smallest available unvisited neighbor first. When there is exactly one cycle (the $m=n$ case), you must try both possible "directions" around the cycle and keep the better resulting sequence.