CF1106D Lunar New Year and a Wander

春节临近，Bob 决定在附近的公园里散步。 这个公园可以用一个连通图来表示，图中有 $n$ 个节点和 $m$ 条无向边。起初，Bob 位于节点 $1$，并且他在笔记本上记录下 $1$。他可以通过这些无向边从一个节点走到另一个节点。每当他到达一个尚未在笔记本上记录的节点时，他就会将其记录下来。当他至少访问过所有节点一次后，他就会停止漫步，因此最终笔记本上会记录下一个节点的排列 $a_1, a_2, \ldots, a_n$。 散步很无聊，但解题很有趣。Bob 想知道，他在漫步过程中能记录下的字典序最小的节点序列是什么。Bob 觉得这个问题很简单，于是想让你来解决。 当且仅当满足下列条件之一时，序列 $x$ 的字典序小于序列 $y$： - $x$ 是 $y$ 的前缀，且 $x \ne 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$。

在第一个样例中，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\}$，这是字典序最小的序列。 由 ChatGPT 4.1 翻译