#MX175. 桥

桥

时间限制:1000ms

空间限制:512MB

题目描述

一条边被称为桥,当且仅当删去该边后,图中的联通块个数增加。

给定 2n2n 个节点的图,图中可以有重边,和长度为 mm 的序列 a,ba,b,对于 1≤i≤m1 \leq i \leq m,都有 1≤ai,bi≤n1 \leq a_i,b_i \leq n​。

图中共有 n+mn+m 条边,其中前 nn 条边中,第 ii 条边连接节点 ii 和 i+ni+n。

你需要构造并给出长度为 mm 的 0101 操作序列 ss,根据你给出的长度为 mm 的操作序列,在原图的基础上加入以下边从而构造无向图:

对于 1≤i≤m1 \leq i \leq m,若 si=s_i= 0,则连接无向边 (ai,bi+n)(a_i,b_i+n),否则连接无向边 (ai+n,bi)(a_i+n,b_i)。

请最小化图中桥的个数,给出你的构造方案。

输入格式

输入第一行,包含 22 个正整数 n,mn,m。

第二行给定长度为 mm 的正整数序列 aa。

第三行给定长度为 mm 的正整数序列 bb。

输出格式

输出一个长度为 mm 的 0101​ 序列,表示答案。

样例 1 输入

2 2
1 1
2 2

样例 1 输出

01

样例解释 1

图中存在边 (1,3)(2,4)(3,2)(1,4)(1,3)(2,4)(3,2)(1,4),不存在桥。

样例 2 输入

4 8
1 2 3 1 1 2 3 4
2 3 4 4 2 3 1 2

样例 2 输出

01000000

样例解释 2

依次连接 $(1,5)(2,6)(3,7)(4,8)(1,6)(6,3)(3,8)(1,8)(1,6)(2,7)(3,5)(4,6)$,图中不存在桥。

样例 3 输入

5 4
1 2 4 3
2 3 1 5

样例 3 输出

0101

样例解释 3

图中有 99 座桥,可以证明不存在桥更少的构造方式。

样例 4 输入

6 6
1 2 3 4 1 1
2 3 4 5 5 6

样例 4 输出

000011

样例解释 4

图中的桥有 (6,7)(6,12)(6,7)(6,12),共 22​​ 座桥。

样例 5 输入

10 10
2 2 4 5 5 6 7 8 9 10
1 3 3 4 6 1 1 1 1 1

样例 5 输出

1011000000

样例 6 输入

10 12
2 2 4 5 5 6 7 8 9 10 8 7
1 3 3 4 6 1 1 1 1 1 10 9

样例 6 输出

101100110000

样例 7~10

见下发文件。

其中样例 88 满足特殊性质 A,BA,B。

其中样例 99 满足特殊性质 A,CA,C。

评测数据规模

测试点编号 nn mm 特殊性质
1,21,2 ≤20\leq 20 无
3,43,4 ≤105\leq 10^5 A,BA,B
5,65,6 A,CA,C
7,8,9,107,8,9,10 无

特殊性质 A : 构造一个 nn 个点 mm 条边的图,其中第 ii 条无向边连接 (ai,bi)(a_i,b_i),保证该图为无重边,无自环的联通图。

特殊性质 B : m=n−1m=n-1。

特殊性质 C : m=nm=n。