分数: 700 点
问题陈述
我们有两个序列 A_1,\ldots, A_M 和 B_1,\ldots,B_M 由之间的整数组成 1 和 N (含)。
对于长度为字符串 M 组成 0 和 1,考虑以下无向图 2N 顶点和 (M+N) 与该字符串对应的边。
- 如果 i字符串的第一个字符是
0, i第一条边连接顶点 A_i 和顶点 (B_i+N). - 如果 i字符串的第一个字符是
1, i第一条边连接顶点 B_i 和顶点 (A_i+N). - 的 (j+M)第一条边连接顶点 j 和顶点 (j+N).
在这里, i 和 j 是整数,使得 1 \leq i \leq M 和 1 \leq j \leq N, 并且顶点已编号 1 to 2N.
查找长度为一的字符串 M 组成 0 和 1 使得相应的无向图具有最少的桥数。
桥梁注意事项
桥是图的边,删除它会增加连接组件的数量。约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \cdots A_M B_1 B_2 \cdots B_M
输出
打印一个满足要求的字符串。如果有多个这样的字符串,您可以打印其中任何一个。
示例输入 1
2 2 1 1 2 2
示例输出 1
01
对应的图表 01 没有桥梁。
图中对应 00,连接顶点的边 1 和顶点 3 和连接顶点的边 2 和顶点 4 是桥梁,所以 00 不满足要求。
示例输入 2
6 7 1 1 2 3 4 4 5 2 3 3 4 5 6 6
示例输出 2
0100010