Problem G
Alternating Current

Fredrik ist zu Hause und spielt mit seiner selbstgebauten Eisenbahn, auf die er sehr stolz ist. Die Eisenbahn besteht aus $N$ im Kreis angeordneten Schienen, die von $1$ bis $N$ im Uhrzeigersinn durchnummeriert sind. Der Zug erhält seinen Strom von $M$ an dem Kreis angebrachten Drähten. An jeder Schiene läuft mindestens eine solchen Draht entlang.

Leider wird Fredrik recht langweilig mit seiner Eisenbahn, die nur im Kreis fährt, woraufhin er entscheidet, eine Weiche zu jeder Schiene hinzuzufügen, um Zugentgleisungen und andere aufregende Szenarios zu verursachen. Aber die Weichen brauchen ebenfalls Elektrizität. Und zwar nicht irgendeinen Strom; Sie brauchen Wechselstrom. ¹

Um Wechselstrom zu bekommen, wird Strom benötigt, der in beide Richtungen fließt. Jeder Draht kann nur Strom in eine Richtung (entweder im Uhrzeigersinn oder gegen den Uhrzeigersinn) liefern, aber Fredrik darf entscheiden, in welche. Er muss also eine Entscheidung für die Stromrichtung jedes Drahtes treffen, um zu erreichen, dass jede Weiche mindestens mit je einem Draht für jede Stromrichtung verbunden ist.

Kannst du Fredrik hierbei helfen?

Eine Lösung des ersten Beispiels. Die gebogenen Pfeile um die Schienen representieren die Drähte, die den Strom liefern. Die Richtung jedes Pfeiles repräsentiert Fredriks Wahl der Richtung des Stromes (wobei die blauen und roten Farben die unterschiedliche Richtungen betonen). Beachte, dass alle Pfeile invertiert werden können, um eine weitere mögliche Lösung zu erzielen: 11010.

Eingabe

Die erste Zeile der Eingabe enthält zwei Zahlen $N$ und $M$, die Anzahl der Schienen und die Anzahl der Drähte.

Die nächsten $M$ Zeilen enthalten jeweils zwei Zahlen $1 \le a, b \le N$, die bedeuten, dass es einen Draht gibt, der die Schienen $a, a+1, \dots , b$ verbindet. Wenn $b$ kleiner als $a$ ist, bedeutet das, dass sich der Draht über den Ursprung hinweg spannt, also über die Schienen $a, \dots , N, 1, \dots , b$. Falls $a=b$, versorgt der Draht nur eine Schiene mit Strom.

Ausgabe

Gib eine einzelne Zeile mit $M$ Zeichen aus, die jeweils 0 oder 1 sein dürfen. Das $i$-te Zeichen soll 0 sein, wenn der Strom im $i$-ten Draht der Eingabe im Uhrzeigersinn ausgerichtet sein soll, und 1, wenn der Strom gegen den Uhrzeigersinn ausgerichtet sein soll. Wenn es mehrere Lösungen gibt, gib eine beliebige davon aus.

Wenn es keine Lösung gibt, gib “impossible” aus.

Beschränkungen

Deine Lösung wird auf mehreren Testgruppen ausgeführt werden, von denen jede eine bestimmte Punktzahl wert ist. Jede Testgruppe enthält mehrere Testcases. Um Punkte für eine Testgruppe zu bekommen, müssen alle Testfälle in der entsprechenden Gruppe gelöst werden. Deine finale Punktzahl wird die maximal erreichte Punktzahl in einer einzelnen Einsendungen sein.

10 5
1 5
6 7
5 1
7 2
2 4

00101

10 5
1 4
2 5
4 7
6 10
8 1

impossible

5 2
1 5
3 3

impossible

5 3
3 3
2 1
4 2

101