P5049 [NOIP 2018 提高组] 旅行 加强版

题目描述

给定一棵树或者一棵基环树（ $n$ 个点 $m$ 条无向边的无自环无重边的连通图，$m = n-1$ 或 $m=n$ ），任选一点出发求字典序最小的遍历顺序（当然选从点 $1$ 出发）。

输入格式

输入文件共 $m + 1$ 行。第一行包含两个整数 $n,m(m \le n)$，中间用一个空格分隔。

接下来 $m$ 行，每行包含两个整数 $u,v (1 \le u,v \le n)$ ，表示点 $u$ 和点 $v$ 之间有一条无向边。

输出格式

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

输入输出样例 #1

输入 #1

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

输出 #1

1 3 2 5 4 6

输入输出样例 #2

输入 #2

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

输出 #2

1 3 2 4 5 6

数据范围与提示

对于全部测试数据，$1 \le n \le 5 \times 10^5$，且 $m = n - 1$ 或 $m = n$。保证 $1 \le u, v \le n$。