CF1133F1.Spanning Tree with Maximum Degree

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 find any spanning tree of this graph such that the maximum degree over all vertices is maximum possible. Recall that the degree of a vertex is the number of edges incident to it.

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

你的任务是找出该图的任意一棵生成树，使得所有顶点中的最大度数尽可能大。注意：一个顶点的度数是指与其关联的边的数量。

The first line 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 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 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.

第一行包含两个整数 $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$。

Print $n-1$ lines describing the edges of a spanning tree such that the maximum degree over all vertices is maximum possible. Make sure that the edges of the printed spanning tree form some subset of the input edges (order doesn't matter and edge $(v, u)$ is considered the same as the edge $(u, v)$).

If there are multiple possible answers, print any of them.

输出 $n-1$ 行，描述一棵生成树的边，使得所有顶点的最大度数尽可能大。请确保所输出的生成树的边是输入边集的某个子集（边的顺序无关紧要，且边 $(v, u)$ 与边 $(u, v)$ 被视为同一条边）。

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

Picture corresponding to the first example:

In this example the number of edges of spanning tree incident to the vertex $3$ is $3$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer.

Picture corresponding to the second example:

In this example the number of edges of spanning tree incident to the vertex $1$ is $3$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer.

Picture corresponding to the third example:

In this example the number of edges of spanning tree incident to the vertex $2$ is $4$. It is the maximum degree over all vertices of the spanning tree. It is easy to see that we cannot obtain a better answer. But because this example is symmetric, we can choose almost the same spanning tree but with vertex $5$ instead of $2$.

对应第一个示例的图片：

在本示例中，生成树中与顶点 $3$ 关联的边的数量为 $3$。该值是该生成树中所有顶点的最大度数。显然，我们无法得到更优的答案。

对应第二个示例的图片：

在本示例中，生成树中与顶点 $1$ 关联的边的数量为 $3$。该值是该生成树中所有顶点的最大度数。显然，我们无法得到更优的答案。

对应第三个示例的图片：

在本示例中，生成树中与顶点 $2$ 关联的边的数量为 $4$。该值是该生成树中所有顶点的最大度数。显然，我们无法得到更优的答案。但由于本示例具有对称性，我们可以选择一个几乎相同的生成树，只是将顶点 $2$ 替换为顶点 $5$。