← 返回题目列表

Codeforces · 1106/D

D. 农历新年和漫步

中文机器翻译题面 查看原题

农历新年即将来临,鲍勃决定去附近的公园散步。

公园可以表示为具有 $$$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\}$$$,这是字典顺序上最小的序列。