CF1133F2 Spanning Tree with One Fixed Degree

给定一个无向、无权、连通的图，该图包含 $n$ 个顶点和 $m$ 条边。保证图中没有自环和重边。 你的任务是找到该图的任意一棵生成树，使得编号为 $1$ 的顶点的度数恰好等于 $D$（或者说明不存在这样的生成树）。回忆一下，顶点的度数是指与该顶点相连的边的数量。

第一行包含三个整数 $n$、$m$ 和 $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 < n$），分别表示顶点数、边数和编号为 $1$ 的顶点在生成树中的度数。 接下来的 $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$。

如果不存在满足条件的生成树，第一行输出 "NO"。 否则，第一行输出 "YES"，接下来输出 $n-1$ 行，每行描述生成树中的一条边，使得编号为 $1$ 的顶点的度数恰好为 $D$。输出的生成树边必须是输入边的子集（顺序不限，边 $(v, u)$ 和 $(u, v)$ 视为同一条边）。 如果有多种方案，输出任意一种均可。

下图对应第一个和第二个样例： 下图对应第三个样例： 由 ChatGPT 4.1 翻译