题目描述

《邻接表bfs（无向连通图）》

给定一个 n 个顶点 m 条边的无向连通图，顶点编号从 1 至 n。对这个图进行广度优先遍历，要求“从顶点1出发，优先访问编号大的顶点”，输出遍历序列。

输入格式

第一行输入两个正整数 n 和 m，表示图的顶点数和边数。1≤n≤1000，1≤m≤10^5。 第二行开始，往后 m 行，每行输入两个以空格隔开的正整数 u,v，表示 u,v 顶点之间有一条边直接相连（u、v是顶点编号，数值范围是1~n）。 本题测试数据确保任意两点之间最多只有1条边、且数据合法，不存在x点到x点有边的情况。

输出格式

输出一行图的遍历序列，顶点编号之间用空格隔开。

样例

输入样例 1

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

输出样例 1

1 6 4 3 2 5

输入样例 2

5 4
1 2
2 3
3 4
4 5

输出样例 2

1 2 3 4 5

输入样例 3

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

输出样例 3

1 6 5 4 3 2

输入样例 4

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

输出样例 4

1 4 3 2