Background

NOIP2018 Senior Group D2T1

Problem Description

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

Little 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. Little Y can only travel between cities using these roads.

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

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

For two sequences $A$ and $B$ both of length $n$, we say that sequence $A$ is lexicographically smaller than sequence $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 following $m$ lines each contain two integers $u, v (1 ≤ u, v ≤ n)$, indicating that there is a road between city $u$ and city $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

[Data Range and Constraints]

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

For different test cases, the data scale is as follows:

见题面 Input 部分

见题面 Output 部分