Problem G
Skiptistraumur

Fredrik er heima að leika sér með sérsmíðuðu lestarteina módeli sem hann er mjög stoltur af. Lestarteinarnir samanstanda af $N$ hlutum sem eru tengdir í hring, númeraðir $1, 2, \dots , N$ réttsælis. Rafstraumur í lestina fer í gegnum $M$ bogna víra sem liggja að hringnum. Hver hluti hefur að minnsta kosti einn vír við sig.

Hinsvegar hefur Fredrik fengið leið á lestinni sinni sem fer bara í hring og hefur ákveðað að bæta við lestrofa á hvern hluta sem hann getur notað til að valda því að lestin fari af lestarteinunum og í aðrar spennandi aðstæður. En rofarnir þurfa rafstraum. Ekki bara einhvern rafstraum, heldur þurfa þeir sérstaklega skiptistraum.¹

Fredrik hugsar að leiðin til að fá skiptistraum er að leiða rafstraum í báðar áttir. Hver vír leiðir straum í eina átt (annað hvort réttsælis eða rangsælis) en Fredrik ræður í hvora átt hver vír leiðir straum. Því vill hann ákveða fyrir hvern vír í hvaða átt sá vír leiðir straum þannig að hver hluti lestarteinanna sé með réttsælis snúinn vír og rangsælis snúinn vír.

Geturðu hjálpað Fredrik?

Lausn við fyrsta sýnidæminu. Bognu örvarnar fyrir utan teinana tákna vírana sem leiða rafstraum. Áttin sem örin bendir í táknar hvaða átt Fredrik valdi fyrir vírinn (þar sem litirnir skýra líka áttirnar). Taktu eftir að snúa má öllum örvunum við til að fá hina gildu lausnina: 11010.

Inntak

Fyrsta línan inniheldur tvær heiltölur $N$ og $M$, fjöldi hluta í lestarteinunum og fjöldi víra.

Næstu $M$ línur innihalda hver tvær heiltölur $1 \le a, b \le N$, sem þýðir að það vírinn liggur við hluta $a, a+1, \dots , b$. Ef $b$ er minna en $a$ þá fer runan fram yfir, þ.e. hlutar $a, \dots , N, 1, \dots , b$ eru tengdir. Taktu eftir að ef $a=b$ þá er aðeins einn hluti í rununni.

Úttak

Skrifaðu út línu með $M$ stöfum, hver annað hvort 0 eða . Stafur númer $i$ í línunni skal vera 0 ef straumurinn á vír númer $i$ á að streyma réttsælis, annars 1 ef hann á að streyma rangsælis. Ef það eru margar lausnir til máttu skrifa út einhverja þeirra.

Ef það eru ekki til neinar gildar lausnir skaltu skrifa út “impossible”.

Takmarkanir

Lausnin þín verður prófuð á einhvern fjölda prufuhópa, hver hópur gefur einhvern fjölda stiga. Hver hópur inniheldur einhvern fjölda prufutilvika. Til að fá stig fyrir hóp þarftu að leysa öll prufutilvik innan hópsins. Lokastigin eru fengin úr skilunum sem gáfu hæst stig.

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