Description

给定一个 n 个结点、m条边的无向图。保证无向图没有重边和自环，且保证图是联通的。

结点的编号为 1 到 n，你可以任选一个结点作为起点，从起点开始你有两种选择：

1. 走向一个没有访问过的结点；
2. 沿着第一次访问该结点时经过的边退回到上一个结点

当你每次访问到一个新结点（包括起点）时，你需要将结点的编号记录到序列 s​ 的末尾。特别地，序列 s​ 的最终长度应为 n​，即能将所有结点都遍历到。

现在问，字典序最小的序列 s。

Input Format

输入共 m+1 行，第一行为两个整数 n,m(m ≤ n)，中间用空格分隔。

接下来 m ，每行两个整数 u,v(1 ≤ u,v ≤ n)，表示编号为 u 的结点和编号为 v 的结点有一条无向边相连，中间用空格分隔。

Output Format

输出共一行， n 个整数，表示字典序最小的序列 s。

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

1 3 2 4 5 6​

Hint

数据范围与约定

对于 50%​​ 的数据来说，m=n-1

对于另外 50%​​ 的数据来说，m=n

对于所有数据来说， 1 ≤ n,m ≤ 5000

挑战

如果 1 ≤ n,m ≤ 500000，此题应如何处理？（本题数据并没有到达这个范围，仅供思考）

由于这般那般的原因，如果你的代码超时，可以尝试在代码开头添加如下部分

#pragma GCC optimize(2)

手动打开O2优化

Source

DFS