CF1680F.Lenient Vertex Cover

You are given a simple connected undirected graph, consisting of $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$.

A vertex cover of a graph is a set of vertices such that each edge has at least one of its endpoints in the set.

Let's call a lenient vertex cover such a vertex cover that at most one edge in it has both endpoints in the set.

Find a lenient vertex cover of a graph or report that there is none. If there are multiple answers, then print any of them.

给你一个简单连通无向图，包含 $n$ 个顶点和 $m$ 条边。顶点编号为 $1$ 到 $n$。

图的一个顶点覆盖（vertex cover）是指一个顶点集合，使得图中的每条边至少有一个端点属于该集合。

我们称一个宽松顶点覆盖（lenient vertex cover）为一种顶点覆盖，其中至多有一条边的两个端点均在该集合中。

请找出该图的一个宽松顶点覆盖；若不存在，则报告无解。若存在多个解，输出任意一个即可。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $m$ ($2 \le n \le 10^6$; $n - 1 \le m \le \min(10^6, \frac{n \cdot (n - 1)}{2})$) — the number of vertices and the number of edges of the graph.

Each of the next $m$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$; $v \neq u$) — the descriptions of the edges.

For each testcase, the graph is connected and doesn't have multiple edges. The sum of $n$ over all testcases doesn't exceed $10^6$. The sum of $m$ over all testcases doesn't exceed $10^6$.

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

For each testcase, the first line should contain YES if a lenient vertex cover exists, and NO otherwise. If it exists, the second line should contain a binary string $s$ of length $n$, where $s_i = 1$ means that vertex $i$ is in the vertex cover, and $s_i = 0$ means that vertex $i$ isn't.

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

对于每个测试用例，第一行应输出 YES（如果存在一个宽松顶点覆盖），否则输出 NO。如果存在这样的覆盖，第二行应输出一个长度为 $n$ 的二进制字符串 $s$，其中 $s_i = 1$ 表示顶点 $i$ 属于该顶点覆盖，而 $s_i = 0$ 表示顶点 $i$ 不属于该顶点覆盖。

如果存在多个合法答案，输出任意一个即可。

Here are the graphs from the first example. The vertices in the lenient vertex covers are marked red.

以下是第一个示例中的图。宽限顶点覆盖（lenient vertex cover）中的顶点标为红色。