CF1176E Cover it!

给定一个无向、无权、连通的图，包含 $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$ 行，每行包含两个整数 $v_i$ 和 $u_i$（$1 \le v_i, u_i \le n$，$u_i \ne v_i$），表示一条连接顶点 $v_i$ 和 $u_i$ 的边。 保证没有自环和重边，即对于每对 $(v_i, u_i)$，不存在另一对 $(v_i, u_i)$ 或 $(u_i, v_i)$，且 $v_i \ne u_i$。保证给定的图是连通的。 保证所有询问中 $\sum m \le 2 \cdot 10^5$。

对于每个询问，输出两行。 第一行输出一个整数 $k$（$1 \le k \le \lfloor\frac{n}{2}\rfloor$），表示被选择的顶点数。 第二行输出 $k$ 个不同的整数 $c_1, c_2, \dots, c_k$，表示被选择的顶点编号，顺序任意。 保证一定存在解。如果有多种方案，你可以输出任意一种。

在第一个询问中，任意一个顶点或任意一对顶点都可以作为答案。  注意你不需要最小化被选择的顶点数。在第二个询问中，选择两个顶点（顶点 $2$ 和 $4$）就足够了，但选择三个顶点也是可以的。  由 ChatGPT 4.1 翻译