给您一个连通、无向且未加权的图,其中包含 $$$n$$$ 个顶点和 $$$m$$$ 个边。请注意边数的限制:$$$m \le n + 2$$$。
假设我们将一些边缘着色为红色,其余边缘着色为蓝色。现在仅考虑红色边缘并计算图中连接组件的数量。令该值为$$$c_1$$$。同样,仅考虑蓝色边缘并计算图中连接组件的数量。令该值为$$$c_2$$$。
找到边缘的颜色分配,以使 $$$c_1+c_2$$$ 的数量最小化。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^5$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n-1 \leq m \leq \min{\left(n+2,\frac{n \cdot (n-1)}{2}\right)}$$$) — 顶点数和分别为边数。 接下来是
$$$m$$$ 行。第 $$$i$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$) 表示第 $$$i$$$ 边位于顶点 $$$u_i$$$ 和 $$$v_i$$$ 之间。保证输入没有多重边或自循环。该图也保证是连通的。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。保证所有测试用例的 $$$m$$$ 总和不超过 $$$2 \cdot 10^6$$$。
输出
对于每个测试用例,输出长度为 $$$m$$$ 的二进制字符串。如果第 $$$i$$$ 边缘应为红色,则字符串的第 $$$i$$$ 个字符应为 1;如果应为蓝色,则为 0。如果有多种方法可以为给出最小答案的边缘分配颜色,您可以输出任何一种。
示例
输入 #1
4 5 7 1 2 2 3 3 4 4 5 5 1 1 3 3 5 4 4 1 2 2 3 1 4 3 4 6 7 1 2 1 3 3 4 4 5 1 4 5 6 6 2 2 1 1 2
输出 #1
0111010 1001 0001111 0
注意
- 第一个测试用例对应的图是:$$$c_1 + c_2 = 1 + 2 = 3$$$
- 第二个测试用例对应的图是:$$$c_1 + c_2 = 2 + 2 = 4$$$