交流電流

フレドリックは家におり、自慢の自作の鉄道模型で遊んでいます。 線路は$N$個のセグメントによって円形に構成されており、時計回りに$1, 2, \dots , N$という番号が付けられています。 電車への電力は、線路のまわりにある$M$個の曲がったケーブルによって供給されます。 それぞれのセグメントには、少なくとも1個のケーブルが乗っています。

しかし、フレドリックは円形の路線に飽きてしまい、それぞれのセグメントに分岐器を付けることにしました。これで、電車を脱線させるなどの遊び方が楽しめます。しかし、分岐器にも電力が必要になります。 さらに、この分岐器は交流電力が必要となります。1

交流電力を送る方法としてフレドリックが考えたのは、電流を双方向に送ることです。 それぞれのケーブルは電流を1方向(時計回り、反時計回りのどちらか)にしか送ることができませんが、 フレドリックはどちらの方向に送るかを選ぶことができます。 したがって、彼はそれぞれのケーブルで電流をどの向きに送るかを決定し、全てのセグメントに時計回り、反時計回りの両方の電流が送られるようにする必要があります。

フレドリックを手伝ってください。

\includegraphics[width=0.5\textwidth ]{alternatingfig.pdf}

最初のサンプルの解です。線路の外側の矢印はケーブルを流れる電流の向き(青と赤の色は方向を強調するために付けています)を表しています。全ての矢印を反転させると異なる解(11010)になることに注意してください。

入力

最初の行は2つの整数$N$$M$です。それぞれ、線路セグメントの数とケーブルの数を表します。

次の$M$行はそれぞれ2つの数$1 \le a, b \le N$です。1つのケーブルがセグメント$a, a+1, \dots , b$をカバーしていることを表します。$b$$a$より小さい場合、末尾から先頭に続いていることを表します。すなわち、$a, \dots , N, 1, \dots , b$をカバーしているということです。なお、$a=b$の場合は、このケーブルが1つのセグメントだけをカバーしていることを表します。

出力

$M$文字を単一行に出力します。それぞれの文字は0または1です。$i$番目の文字は入力における$i$番目のケーブルを流れる電流の向きに対応し、0は時計回り、1は反時計回りを表します。 複数の解が存在する場合でも、いずれか1つの解を出力してください。

もし解が存在しない場合、“impossible”を出力してください。

制約

あなたのソリューションは、テストグループのセットでテストされ、それぞれのグループにポイントが定義されています。 各テストグループにはテストケースのセットが含まれています。 テストグループのポイントを得るためには、テストグループ内のすべてのテストケースが成功する必要があります。 あなたの最終的なスコアは、1回の提出での最大スコアとなります。

グループ

ポイント

制限

追加の制約

1

13

$2 \le N, M \le 15$

 

2

20

$2 \le N, M \le 100$

 

3

22

$2 \le N, M \le 1000$

 

4

19

$2 \le N, M \le 100\, 000$

No wire has $b < a$.

5

26

$2 \le N, M \le 100\, 000$

 

Footnotes

  1. なぜなら、この鉄道模型はスウェーデン製で、スウェーデンでは全ての分岐器(“växlar”)が交流電力(“växelström”)で動作するためです。(訳注)スウェーデン語で綴りが似ているという冗談