农历新年即将来临,鲍勃决定去附近的公园散步。
公园可以表示为具有 $$$n$$$ 个节点和 $$$m$$$ 双向边的连通图。最初,Bob 位于节点 $$$1$$$,他在笔记本上记录了 $$$1$$$。他可以通过这些双向边缘从一个节点漫游到另一个节点。每当他访问笔记本上未记录的节点时,他都会记录下来。当他访问所有节点至少一次后,他就停止徘徊,从而最终记录了节点 $$$a_1, a_2, \ldots, a_n$$$ 的排列。
流浪是一件无聊的事情,但解决问题却很有趣。鲍勃想知道他在漫游时可以记录的按字典顺序排列的最小节点序列。鲍勃认为这个问题很微不足道,他希望你解决它。
当且仅当满足以下条件之一时,序列 $$$x$$$ 按字典顺序小于序列 $$$y$$$:
- $$$x$$$ 是 $$$y$$$ 的前缀,但是 $$$x \ne y$$$ (在这个问题中这是不可能的,因为所有考虑的序列都具有相同的长度);
- 在 $$$x$$$ 和 $$$y$$$ 不同的第一个位置,序列 $$$x$$$ 的元素比 $$$y$$$ 中的相应元素小。
输入
第一行包含两个正整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 10^5$$$),分别表示节点和边的数量。
以下 $$$m$$$ 行描述了图中的双向边。这些行中的第 $$$i$$$ 包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$),表示第 $$$i$$$ 条边连接的节点。
请注意,该图可以具有连接相同两个节点和自循环的多条边。保证图是连通的。
输出
输出一行,其中包含 Bob 可以记录的字典顺序最小序列 $$$a_1, a_2, \ldots, a_n$$$。
示例
输入 #1
3 2 1 2 1 3
输出 #1
1 2 3
输入 #2
5 5 1 4 3 4 5 4 3 2 1 5
输出 #2
1 4 3 2 5
输入 #3
10 10 1 4 6 8 2 5 3 7 9 4 5 6 3 4 8 10 8 9 1 10
输出 #3
1 4 3 7 9 8 6 5 2 10
注意
在第一个样本中,Bob 的最佳漫游路径可能是 $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 3$$$。因此,Bob 将获得序列 $$$\{1, 2, 3\}$$$,这是字典顺序上最小的序列。
在第二个样本中,Bob 的最佳徘徊路径可能是 $$$1 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 5$$$。因此,Bob 将获得序列 $$$\{1, 4, 3, 2, 5\}$$$,这是字典顺序上最小的序列。