给你一个无向无权连通图,由 $$$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$$$),但三个也可以。