给你一个无向无权连通图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。保证给定图中不存在自环或重边。
你的任务是找到该图的任何生成树,使得第一个顶点(其上带有标签 $$$1$$$ 的顶点)的度等于 $$$D$$$ (或者说不存在这样的生成树)。回想一下,顶点的度数是与其相关的边的数量。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$D$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2}), 1 \le D < n$$$) — 数字分别是顶点数、边数和第一个顶点所需的度数。
下面的 $$$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$$$。
输出
如果没有生成树满足问题陈述中的条件,则在第一行打印“NO”。
否则在第一行打印“YES”,然后打印描述生成树边的 $$$n-1$$$ 行,使得第一个顶点(其上带有标签 $$$1$$$ 的顶点)的度等于 $$$D$$$。确保打印的生成树的边形成输入边的某个子集(顺序无关紧要,边 $$$(v, u)$$$ 被认为与边 $$$(u, v)$$$ 相同)。
如果有多个可能的答案,请打印其中任何一个。
示例
输入 #1
4 5 1 1 2 1 3 1 4 2 3 3 4
输出 #1
YES 2 1 2 3 3 4
输入 #2
4 5 3 1 2 1 3 1 4 2 3 3 4
输出 #2
YES 1 2 1 3 4 1
输入 #3
4 4 3 1 2 1 4 2 3 3 4
输出 #3
NO
注意
第一、第二个例子对应的图片:
第三个例子对应的图片: