← 返回题目列表

Codeforces · 1133/F1

F1. 最大度的生成树

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

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