Problem G
Växelström

Fredrik är hemma och leker med sin hemmabyggda modelljärnväg, som han är mycket stolt över. Järnvägen består av $N$ segment som sitter ihop i en cirkel, numrerade $1, 2, \dots , N$ i medurs ordning. Tåget får elektricitet från vajrar som leder längs cirkeln. Varje segment har minst en vajer längsmed sig.

Fredrik tycker att hans cirkulära tåg börjar bli tråkigt, och bestämmer sig för att lägga till en järnvägsväxel till varje segment, som han kan använda för att skapa urspårningsolyckor och andra spännande scenarier. Växlarna behöver dock elektricitet, och inte vilken elektricitet som helst. De behöver växelström, strömmen som driver växlar.

Fredrik inser att sättet man får växelström på är att ha ström i båda riktningarna. Varje vajer kan endast leda ström i en riktning, antingen medurs eller moturs, men Fredrik kan bestämma riktningen. Han vill alltså bestämma strömriktning på vajrarna så att varje segment är täckt av både en vajer med medurs strömriktning och en med moturs strömrikting.

Kan du hjälpa Fredrik att bestämma riktningarna?

En lösning till det första testfallet. De krökta pilarna utanför järnvägen representerar vajrar som leder ström. Rikningen på pilarna representerar Fredriks val av strömriktning (vilket förtydligas av blå och röda färger på pilarna). Notera att alla strömriktningar kunde ha bytts för att få den andra giltiga lösningen: 11010.

Indata

Den första raden innehåller två heltal $N$ och $M$, antalet järnvägssegment och antalet vajrar.

Följande $M$ rader innehåller två heltal $1 \le a, b \le N$, vilket indikerar att en vajer går längs segmenten
$a, a+1, \dots , b$. Om $b$ är mindre än $a$, så ”wrappas det runt” så att vajern går längs segmenten
$a, a+1, \dots , N, 1, \dots , b$. Notera att om $a=b$ täcker vajern bara ett segment.

Utdata

Skriv ut en enda rad med $M$ tecken, vilka är antingen 0 or 1. Det $i$:te tecknet ska vara 0 om den $i$:te vajern i indatan har medurs strömriktning, medan tecknet ska vara 1 om vajern har moturs strömriktning. Om det finns många lösningar kan du skriva ut vilken som av dem.

Om det är omöjligt att välja strömriktning på vajrarna så att varje segment täcks av en med medursriktad ström och en med motursriktad ström, skriv ut “impossible”.

Begränsningar

Din lösning kommer att testas på en uppsättning testgrupper, var och en värd en viss poäng. Varje testgrupp innehåller flera testfall. För att få poäng för en testgrupp måste du klara alla testfallen i gruppen. Din slutgiltiga poäng på problemet kommer att vara den maximala poängen av en enda submission.

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