给你一个无向无权连通图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。保证给定图中不存在自环或重边。
您的任务是找到该图的任何生成树,使得所有顶点的最大度数成为最大可能。回想一下,顶点的度数是与其相关的边的数量。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$) — 分别是顶点和边的数量。
下面的 $$$m$$$ 行表示边:边 $$$i$$$ 由一对整数 $$$v_i$$$、$$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$, $$$u_i \ne v_i$$$) 表示,它们是边连接的顶点的索引。给定图中没有循环或多重边,i。 e.对于每对 ($$$v_i, u_i$$$),边列表中没有其他对 ($$$v_i, u_i$$$) 或 ($$$u_i, v_i$$$),并且对于每对 $$$(v_i, u_i)$$$ 满足条件 $$$v_i \ne u_i$$$。
输出
打印描述生成树边的 $$$n-1$$$ 行,使得所有顶点的最大度数尽可能最大。确保打印的生成树的边形成输入边的某个子集(顺序无关紧要,边 $$$(v, u)$$$ 被认为与边 $$$(u, v)$$$ 相同)。
如果有多个可能的答案,请打印其中任何一个。
示例
输入 #1
5 5 1 2 2 3 3 5 4 3 1 5
输出 #1
3 5 2 1 3 2 3 4
输入 #2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
输出 #2
4 1 1 2 1 3
输入 #3
8 9 1 2 2 3 2 5 1 6 3 4 6 5 4 5 2 7 5 8
输出 #3
3 2 2 5 8 5 6 1 2 7 1 2 3 4
注意
第一个例子对应的图片:
在此示例中,与顶点 $$$3$$$ 相关的生成树边的数量为 $$$3$$$。它是生成树所有顶点的最大度数。不难看出,我们无法得到更好的答案。
第二个例子对应的图片:
在此示例中,与顶点 $$$1$$$ 相关的生成树边的数量为 $$$3$$$。它是生成树所有顶点的最大度数。不难看出,我们无法得到更好的答案。
第三个例子对应的图片:
在此示例中,与顶点 $$$2$$$ 相关的生成树边的数量为 $$$4$$$。它是生成树所有顶点的最大度数。不难看出,我们无法得到更好的答案。但因为这个例子是对称的,所以我们可以选择几乎相同的生成树,但顶点为 $$$5$$$ 而不是 $$$2$$$。