来源：张老师 2026 CSP-J 4＋1 拓展题 20 套；第 19 套，第 5 题。原题标号：E；原本地编号：Z4P1-19-E。

问题描述

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

给定 $2n$ 个节点的图，图中可以有重边，和长度为 $m$ 的序列 $a,b$，对于 $1 \leq i \leq m$，都有 $1 \leq a_i,b_i \leq n$​。

图中共有 $n+m$ 条边，其中前 $n$ 条边中，第 $i$ 条边连接节点 $i$ 和 $i+n$。

你需要构造并给出长度为 $m$ 的 $01$ 操作序列 $s$，根据你给出的长度为 $m$ 的操作序列，在原图的基础上加入以下边从而构造无向图：

对于 $1 \leq i \leq m$，若 $s_i=$ 0，则连接无向边 $(a_i,b_i+n)$，否则连接无向边 $(a_i+n,b_i)$。

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

输入格式

输入第一行，包含 $2$ 个正整数 $n,m$。

第二行给定长度为 $m$ 的正整数序列 $a$。

第三行给定长度为 $m$ 的正整数序列 $b$。

输出格式

输出一个长度为 $m$ 的 $01$​ 序列，表示答案。

样例输入1

2 2
1 1
2 2

样例输出1

01

样例解释

图中存在边 $(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

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

样例输入4

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

样例输出4

000011

样例解释4

图中的桥有 $(6,7)(6,12)$，共 $2$​​ 座桥。

样例输入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,8,9,10

见下发文件。

其中样例 $8$ 满足特殊性质 $A,B$。

其中样例 $9$ 满足特殊性质 $A,C$。

评测数据规模

测试点编号	$n$	$m$	特殊性质
$1,2$	$\leq 20$		无
$3,4$	$\leq 10^5$		$A,B$
$5,6$			$A,C$
$7,8,9,10$			无

特殊性质 A : 构造一个 $n$ 个点 $m$ 条边的图，其中第 $i$ 条无向边连接 $(a_i,b_i)$，保证该图为无重边，无自环的联通图。

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

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