← 返回题目列表

Codeforces · 1133/F2

F2. 具有一个固定度数的生成树

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

给你一个无向无权连通图,由 $$$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

注意

第一、第二个例子对应的图片:

第三个例子对应的图片: