CF723F st-Spanning Tree

给定一个包含 $n$ 个顶点和 $m$ 条边的无向连通图。图中不存在自环和重边。 同时，给定两个不同的顶点 $s$ 和 $t$，以及两个值 $d_s$ 和 $d_t$。你的任务是：在该图中构造一棵生成树（注意图是无权的），使得顶点 $s$ 的度数不超过 $d_s$，顶点 $t$ 的度数不超过 $d_t$，或者判断不存在这样的生成树。 图 $G$ 的生成树是其一个包含所有顶点且是树的子图。换句话说，它是一个连通且包含 $n-1$ 条边的子图，可以通过从 $G$ 中删除部分边得到。 顶点的度数指与该顶点相连的边的条数。

输入的第一行为两个整数 $n$ 和 $m$（$2 \le n \le 200000$，$1 \le m \le \min(400000, n \cdot (n-1) / 2)$），表示图中顶点和边的数量。 接下来的 $m$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示一条连接 $u$ 和 $v$ 的无向边。保证图中无自环、无重边，且图是连通的。 最后一行为四个整数 $s$、$t$、$d_s$、$d_t$（$1 \le s, t \le n$，$s \ne t$，$1 \le d_s, d_t \le n-1$）。

如果不存在满足条件的生成树，输出一行 “No”。 否则，第一行输出 “Yes”。接下来的 $n-1$ 行，每行输出两个整数，表示生成树中的一条边。每条边只能输出一次，顺序不限，边的两端顺序也不限。 如果有多组解，输出任意一组均可。

由 ChatGPT 5 翻译