CF1133F2.Spanning Tree with One Fixed 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 degree of the first vertex (vertex with label $1$ on it) is equal to $D$ (or say that there are no such spanning trees). Recall that the degree of a vertex is the number of edges incident to it.

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

你的任务是找出该图的任意一棵生成树，使得第一个顶点（标号为 $1$ 的顶点）的度数恰好等于 $D$（若不存在这样的生成树，则需说明这一点）。注意：一个顶点的度数是指与其关联的边的数量。

The first line contains three integers $n$, $m$ and $D$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le min(2 \cdot 10^5, \frac{n(n-1)}{2}), 1 \le D \lt n$) — the number of vertices, the number of edges and required degree of the first vertex, 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$ 和 $D$（$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)$，$1 \le D < n$），分别表示顶点数、边数以及第一个顶点所需满足的度数。

接下来的 $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$。

If there is no spanning tree satisfying the condition from the problem statement, print "NO" in the first line.

Otherwise print "YES" in the first line and then print $n-1$ lines describing the edges of a spanning tree such that the degree of the first vertex (vertex with label $1$ on it) is equal to $D$. 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.

如果不存在满足题目条件的生成树，则在第一行输出 “NO”。

否则，在第一行输出 “YES”，然后输出 $n-1$ 行，描述一棵生成树的边，使得第一个顶点（标号为 $1$ 的顶点）的度数恰好等于 $D$。请确保所输出生成树的边均属于输入边集（顺序无关，并且边 $(v, u)$ 与边 $(u, v)$ 被视为同一条边）。

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

The picture corresponding to the first and second examples:

The picture corresponding to the third example:

第一个和第二个示例对应的图片：

第三个示例对应的图片：