D - Bridges Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 つ出力せよ．答えが複数存在する場合，いずれを出力してもかまわない．

入力例 1

2 2
1 1
2 2

出力例 1

01

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

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

入力例 2

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

出力例 2

0100010

Score : 700 points

Problem Statement

We have two sequences A_1,\ldots, A_M and B_1,\ldots,B_M consisting of intgers between 1 and N (inclusive).

For a string of length M consisting of 0 and 1, consider the following undirected graph with 2N vertices and (M+N) edges corresponding to that string.

  • If the i-th character of the string is 0, the i-th edge connects Vertex A_i and Vertex (B_i+N).
  • If the i-th character of the string is 1, the i-th edge connects Vertex B_i and Vertex (A_i+N).
  • The (j+M)-th edge connects Vertex j and Vertex (j+N).

Here, i and j are integers such that 1 \leq i \leq M and 1 \leq j \leq N, and the vertices are numbered 1 to 2N.

Find one string of length M consisting of 0 and 1 such that the corresponding undirected graph has the minimum number of bridges.

Notes on bridges A bridge is an edge of a graph whose removal increases the number of connected components.

Constraints

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

Input

Input is given from Standard Input in the following format:

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

Output

Print one string that satisfies the requirement. If there are multiple such strings, you may print any of them.

Sample Input 1

2 2
1 1
2 2

Sample Output 1

01

The graph corresponding to 01 has no bridges.

In the graph corresponding to 00, the edge connecting Vertex 1 and Vertex 3 and the edge connecting Vertex 2 and Vertex 4 are bridges, so 00 does not satisfy the requirement.

Sample Input 2

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

Sample Output 2

0100010