配点 : $700$ 点

問題文

$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$ つ求めてください．

制約

• $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

01

01 に対応するグラフには橋が存在しません．

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

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

0100010