CF1176E.Cover it!

You are given an undirected unweighted connected graph consisting of $n$ vertices and $m$ edges. It is guaranteed that there are no self-loops or multiple edges in the given graph.

Your task is to choose at most $\lfloor\frac{n}{2}\rfloor$ vertices in this graph so each unchosen vertex is adjacent (in other words, connected by an edge) to at least one of chosen vertices.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.

You will be given multiple independent queries to answer.

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

你的任务是从此图中选出至多 $\lfloor\frac{n}{2}\rfloor$ 个顶点，使得每个未被选中的顶点至少与一个被选中的顶点相邻（即通过一条边相连）。

保证答案一定存在。若存在多个合法答案，输出任意一个即可。

你将收到多个相互独立的查询，需分别作答。

The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^5$) — the number of queries.

Then $t$ queries follow.

The first line of each query contains two integers $n$ and $m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2})$) — the number of vertices and the number of edges, respectively.

The following $m$ lines denote edges: edge $i$ is represented by a pair of integers $v_i$, $u_i$ ($1 \le v_i, u_i \le n$, $u_i \ne v_i$), which are the indices of vertices connected by the edge.

There are no self-loops or multiple edges in the given graph, i. e. for each pair ($v_i, u_i$) there are no other pairs ($v_i, u_i$) or ($u_i, v_i$) in the list of edges, and for each pair ($v_i, u_i$) the condition $v_i \ne u_i$ is satisfied. It is guaranteed that the given graph is connected.

It is guaranteed that $\sum m \le 2 \cdot 10^5$ over all queries.

第一行包含一个整数 $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\left(2 \cdot 10^5, \frac{n(n-1)}{2}\right)$）—— 分别表示顶点数和边数。

接下来的 $m$ 行描述各条边：第 $i$ 条边由一对整数 $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)$ 或反向的 $(u_i, v_i)$；且对任意一对 $(v_i, u_i)$ 均满足 $v_i \ne u_i$。保证给定图是连通的。

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

For each query print two lines.

In the first line print $k$ ($1 \le \lfloor\frac{n}{2}\rfloor$) — the number of chosen vertices.

In the second line print $k$ distinct integers $c_1, c_2, \dots, c_k$ in any order, where $c_i$ is the index of the $i$-th chosen vertex.

It is guaranteed that the answer exists. If there are multiple answers, you can print any.

对每个查询，输出两行。

第一行输出 $k$（$1 \le \lfloor\frac{n}{2}\rfloor$）—— 即所选顶点的个数。

第二行以任意顺序输出 $k$ 个互不相同的整数 $c_1, c_2, \dots, c_k$，其中 $c_i$ 表示第 $i$ 个所选顶点的下标。

保证答案存在。若存在多个答案，输出任意一个即可。

In the first query any vertex or any pair of vertices will suffice.

Note that you don't have to minimize the number of chosen vertices. In the second query two vertices can be enough (vertices $2$ and $4$) but three is also ok.

在第一次查询中，任意一个顶点或任意一对顶点均可满足要求。

注意：你无需最小化所选顶点的数量。在第二次查询中，两个顶点可能已足够（例如顶点 $2$ 和 $4$），但选择三个顶点也是可以接受的。