题目描述

$1$ 以上 $N$ 以下の整数からなる $2$ つの数列 $A_1,\ldots,\ A_M$ および $B_1,\ldots,B_M$ があります．

0 と 1 からなる長さ $M$ の文字列に対して，$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$ から $2N$ までの番号がついています．

対応する無向グラフに含まれる橋の個数が最小となるような，0 と 1 からなる長さ $M$ の文字列を $1$ つ求めてください．

橋について グラフの辺であって，その辺を除くと連結成分の個数が増えるようなものを橋と呼びます．

输入格式

入力は以下の形式で標準入力から与えられる．

$N$ $M$ $A_1$ $A_2$ $\cdots$ $A_M$ $B_1$ $B_2$ $\cdots$ $B_M$

输出格式

条件を満たすような文字列を $1$ つ出力せよ．答えが複数存在する場合，いずれを出力してもかまわない．

题目大意

有两个长度为 $M$ 的整数数组 $A_1 \dots A_M ,B_1 \dots B_M$。保证 $1 \le A_i,B_i \le N$。现在有一个 $2N$ 个编号从 $1$ 到 $2N$ 的点的无向图，初始时第 $i$ 与 第 $i+N$ 号点相连，现在对于长为 $M$ 的 $0/1$ 串。

• 若 $M_i=0$ 则连接一条 $(A_i,B_{i}+N)$ 的无向边。
• 若 $M_i=1$ 则连接一条 $(A_{i}+N,B_i)$ 的无向边。

现在请你构造出一个长为 $M$ 的 $0/1$ 串，使得此无向图的桥最少。

数据范围

$1 \le N,M \le 2 \times 10^5$

$1 \le A_i,B_i \le N$

输入格式

第一行两个整数 $N,M$。

第二行 $M$ 个整数 $A_1 \dots A_M$。

第三行 $M$ 个整数 $B_1 \dots B_M$。

2 2
1 1
2 2

01

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

0100010

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ M\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i,\ B_i\ \leq\ N$

Sample Explanation 1

01 に対応するグラフには橋が存在しません． 00 に対応するグラフでは頂点 $1$ と頂点 $3$ を結ぶ辺と頂点 $2$ と頂点 $4$ を結ぶ辺が橋となるので， 00 は条件を満たしません．