← 返回题目列表

Codeforces · 1680/F

F. 宽松的顶点覆盖

中文机器翻译题面 查看原题

给你一个简单的连通无向图,由 $$$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$$$ 表示顶点 $$$i$$$ 不在顶点覆盖中。

如果有多个答案,则打印其中任何一个。

示例

输入 #1

4
6 5
1 3
2 4
3 4
3 5
4 6
4 6
1 2
2 3
3 4
1 4
1 3
2 4
8 11
1 3
2 4
3 5
4 6
5 7
6 8
1 2
3 4
5 6
7 8
7 2
4 5
1 2
2 3
3 4
1 3
2 4

输出 #1

YES
001100
NO
YES
01100110
YES
0110

输入 #2

1
10 15
9 4
3 4
6 4
1 2
8 2
8 3
7 2
9 5
7 8
5 10
1 4
2 10
5 3
5 7
2 9

输出 #2

YES
0101100100

输入 #3

1
10 19
7 9
5 3
3 4
1 6
9 4
1 4
10 5
7 1
9 2
8 3
7 3
10 9
2 10
9 8
3 2
1 5
10 7
9 5
1 2

输出 #3

YES
1010000011

注意

这是第一个示例的图表。宽松顶点覆盖中的顶点标记为红色。