Problem G
Kintamoji srovė

Fredrikas namuose žaidžia savo suprojektuotu geležinkelio modeliu, kuriuo jis labai didžiuojasi. Geležinkelį sudaro $N$ segmentų, sujungtų į apskritimą, ir sunumeruotų $1, 2, \dots , N$ pagal laikrodžio rodyklę. Elektra traukiniui tiekiama $M$ kabelių, nutiestų virš apskritimo, kuriuo eina geležinkelio bėgiai. Kiekvienam segmentui yra bent vienas kabelis, nutiestas virš to segmento.

Fredrikui pabodo ratu važinėjantis traukinys ir jis nutarė prie kiekvieno segmento pridėti po jungiklį, kuriais naudodamasis jis galėtų nuversti traukinį nuo bėgių ar sukelti kitus įdomius įvykius. Tačiau jungikliams irgi reikia tiekti elektrą. Ir ne bet kokią, o kintamos srovės.¹

Fredrikas gaus kintamą srovę, jei turės abiem kryptimis tekančią srovę. Kiekvienu kabeliu srovė teka tik viena kryptimi (prieš ar pagal laikrodžio rodyklę), tačiau Fredrikas gali parinkti kryptį, kuria tekės srovė. Taigi, jis nori parinkti srovės tekėjimo kryptį kiekviename kabelyje taip, kad kiekvienas bėgių segmentas būtų uždengtas ir pagal, ir prieš laikrodžio rodyklę einančią srovę duodančiais kabeliais.

Padėkite Fredrikui išspręsti šį uždavinį.

Pirmojo pavyzdžio sprendimas. Išlenktos rodyklės reiškia elektrą tiekiančius kabelius. Rodyklės kryptis nurodo Fredriko pasirinktą elektros srovės kryptį (mėlyna ir raudona spalvos paryškina priešingas kryptis). Atkreipkite dėmesį, kad apsukę visas rodykles, gautume kitą galimą sprendimą: 11010.

Pradiniai duomenys

Pirmoje eilutėje pateikti du sveikieji skaičiai $N$ ir $M$ – segmentų ir kabelių skaičius.

Kiekvienoje tolesnių $M$ eilučių yra po du skaičius $1 \le a, b \le N$, nurodančius, kad yra kabelis, dengiantis segmentus $a, a+1, \dots , b$. Jei $b$ mažesnis nei $a$, tai reiškia, kad dengiami segmentai $a, \dots , N, 1, \dots , b$. Tačiau jei $a=b$, kabelis dengia tik vieną segmentą.

Rezultatai

Išveskite vieną eilutę su $M$ simbolių, kurie būtų 0 arba 1. $i$-asis eilutės simbolis turi būti 0, jei $i$-uoju kabeliu srovė teka pagal laikrodžio rodyklę, arba 1, jei ji teka prieš laikrodžio rodyklę. Jei yra daugiau nei vienas galimas sprendinys, išveskite bet kurį.

Jei sprendinys neegzistuoja, išveskite “impossible”.

Ribojimai

Jūsų sprendimas bus testuojamas su keliomis testų grupėmis, kiekviena kurių vertinama tam tikru skaičiumi taškų. Kiekvieną testų grupę sudarys keletas testų. Taškai už testų grupę skiriami tik jei įveikiate visus tos grupės testus.

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