普及模拟赛 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$ 序列，表示答案。

2 2
1 1
2 2

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

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

01000000

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

5 4
1 2 4 3
2 3 1 5

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

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

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

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

1011000000

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

101100110000

见下发文件。

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

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

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

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

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

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