给你一个简单的连通无向图,由 $$$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
注意
这是第一个示例的图表。宽松顶点覆盖中的顶点标记为红色。