問題文

NPCA 校には 2N 人の生徒がおり、各生徒には 1 から 2N の順番が付けられています。なぷか君は NPCA 校の教師で、生徒を N 人ずつの 2 つのクラスに分けることになりました。

ここで、クラス分けの不満度を以下のように定義します。

• 整数 i(1 \le i \le M) のうち、生徒 A_i と生徒 B_i が同じクラスにいるもの全てに対する 2^i の総和

なぷか君のために、不満度が最小となるクラス分けの方法を 1 つ構築してください。

制約

• 1 \le N\le 5000
• 0 \le M\le 10^6
• 1\le A_i< B_i \le 2N
• i\ne j ならば (A_i,B_i)\ne (A_j,B_j)
• 入力される値はすべて整数

入力例 1

2 4
1 3
2 4
1 4
1 2

出力例 1

0101

生徒 1 と生徒 3 からなるクラスと生徒 2 と生徒 4 からなるクラスに分けたとき、不満度は以下のように計算されます。

• i=1 について、生徒 1 と生徒 3 は同じクラスである。
• i=2 について、生徒 2 と生徒 4 は同じクラスである。
• i=3 について、生徒 1 と生徒 4 は異なるクラスである。
• i=4 について、生徒 1 と生徒 2 は異なるクラスである。

以上よりこのクラス分けの不満度は 2^1 + 2^2 = 6 であり、この分け方が最小です。1010 を出力してもよいです。

0111 のように分けると不満度は 4 ですが、N 人ずつのクラスに分かれていないため条件を満たしません。

入力例 2

1 0

出力例 2

01

入力例 3

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

出力例 3

011010