CF1680F Lenient Vertex Cover

给定一个简单连通无向图，包含 $n$ 个顶点和 $m$ 条边。顶点编号为 $1$ 到 $n$。 一个顶点覆盖是指一个顶点集合，使得每条边至少有一个端点在该集合中。 我们称“宽松顶点覆盖”为：在该顶点覆盖中，至多只有一条边的两个端点都在集合中。 请你找出该图的一个宽松顶点覆盖，或者报告不存在。如果有多个答案，输出任意一个即可。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 10^6$；$n-1 \le m \le \min(10^6, \frac{n \cdot (n - 1)}{2})$），分别表示图的顶点数和边数。 接下来的 $m$ 行，每行包含两个整数 $v$ 和 $u$（$1 \le v, u \le n$；$v \neq u$），表示一条边的两个端点。 对于每个测试用例，保证图是连通的且没有重边。所有测试用例中 $n$ 的总和不超过 $10^6$，$m$ 的总和不超过 $10^6$。

对于每个测试用例，第一行输出 YES 如果存在宽松顶点覆盖，否则输出 NO。如果存在，第二行输出一个长度为 $n$ 的二进制字符串 $s$，其中 $s_i = 1$ 表示第 $i$ 个顶点在顶点覆盖中，$s_i = 0$ 表示不在。 如果有多个答案，输出任意一个即可。

以下是第一个示例中的图。宽松顶点覆盖中的顶点用红色标记。  由 ChatGPT 4.1 翻译