← 返回题目列表

AtCoder · arc143_d

D. 桥梁

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

分数: 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