AT_npcapc_2024_o New School Term

NPCA 校には $ 2N $ 人の生徒がおり、各生徒には $ 1 $ から $ 2N $ の順番が付けられています。なぷか君は NPCA 校の教師で、生徒を **$ N $ 人ずつの** $ 2 $ つのクラスに分けることになりました。 ここで、クラス分けの不満度を以下のように定義します。 - 整数 $ i(1 \le i \le M) $ のうち、生徒 $ A_i $ と生徒 $ B_i $ が同じクラスにいるもの全てに対する $ 2^i $ の総和 なぷか君のために、不満度が最小となるクラス分けの方法を $ 1 $ つ構築してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

以下のように出力せよ。 > $ S_1 S_2 \dots S_{2N} $ ここで、 $ S_i $ は `0` か `1` のいずれかであり、生徒 $ i $ がどちらのクラスに属するかを示すものとする。 条件を満たすクラス分けが複数存在する場合は、どれを出力しても正解となる。

### Sample Explanation 1 生徒 $ 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 $ 人ずつのクラスに分かれていないため条件を満たしません。 ### Constraints - $ 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) $ - 入力される値はすべて整数