← 返回题目列表

Codeforces · 1726/D

D. 边缘分裂

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

给您一个连通、无向且未加权的图,其中包含 $$$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$$$