← 返回题目列表

Codeforces · 1176/E

E. 盖住它!

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

给你一个无向无权连通图,由 $$$n$$$ 个顶点和 $$$m$$$ 个边组成。保证给定图中不存在自环或重边。

您的任务是在此图中最多选择 $$$\lfloor\frac{n}{2}\rfloor$$$ 个顶点,以便每个未选择的顶点与至少一个选定的顶点相邻(换句话说,通过边连接)。

保证答案存在。如果有多个答案,您可以打印任何一个。

您将需要回答多个独立的问题。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 查询数。

然后是 $$$t$$$ 查询。

每个查询的第一行包含两个整数 $$$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$$$。保证给定的图是连通的。

保证所有查询的 $$$\sum m \le 2 \cdot 10^5$$$ 。

输出

对于每个查询打印两行。

在第一行打印 $$$k$$$ ($$$1 \le \lfloor\frac{n}{2}\rfloor$$$) — 所选顶点的数量。

在第二行中以任意顺序打印 $$$k$$$ 不同的整数 $$$c_1, c_2, \dots, c_k$$$,其中 $$$c_i$$$ 是第 $$$i$$$ 个选定顶点的索引。

保证答案存在。如果有多个答案,您可以打印任何一个。

示例

输入 #1

2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
6 8
2 5
5 4
4 3
4 1
1 3
2 3
2 6
5 6

输出 #1

2
1 3
3
4 3 6

注意

在第一个查询中,任何顶点或任何顶点对就足够了。

请注意,您不必最小化所选顶点的数量。在第二个查询中,两个顶点就足够了(顶点 $$$2$$$ 和 $$$4$$$),但三个也可以。