Problem G
Vahelduvvool

Fredrik mängib kodus iseehitatud mudelraudteega, mille üle ta on väga uhke. Raudtee koosneb $N$ lõigust, mis on ühendatud ringiks ja nummerdatud päripäeva $1, 2, \dots , N$. Rong saab elektrivoolu $M$ juhtmekaare kaudu, mis on paigutatud piki raudteed. Iga raudteelõik on kaetud vähemalt ühe juhtmekaarega.

Fredrik on aga ringiratast sõitvast rongist tüdinud ja otsustab iga lõigu juurde lisada raudteepöörme, mida ta saaks kasutada rongide raudteelt maha juhtimiseks. Pöörmed nõuavad samuti elektrivoolu, täpsemalt vahelduvvoolu. ¹

Fredrik arvab, et vahelduvvoolu saab, kui elektrivool saab minna mõlemas suunas. Igas juhtmes saab vool minna ainult ühes Fredriku valitud suunas (päripäeva või vastupäeva). Seega tahab ta määrata iga juhtme elektrivoolu suuna nii, et iga raudteelõik oleks kaetud nii päripäeva liikuva elektrivooluga juhtmega kui ka vastupäeva vooluga juhtmega.

Kas saad Fredrikut aidata?

Esimese näite lahendus. Nooled raudteest väljaspool tähistavad elektrivooluga juhtmekaari. Iga noole suund näitab voolu suunda (sinised ja punased nooled näitavad eri suundasid). Paneme tähele, et kõigi noolte ümberpööramisel saame teise õige lahenduse: 11010.

Sisend

Esimesel real on kaks täisarvu $N$ ja $M$, vastavalt raudteelõikude arv ja juhtmekaarte arv.

Järgmisel $M$ real on igaühel kaks arvu $1 \le a, b \le N$, mis näitavad, et lõike $a, a+1, \dots , b$ katab üks juhe. Kui $b$ on väiksem kui $a$, tähendab see, et kaar läheb üle $N$ ja $1$ ühenduskoha, st lõigud $a, \dots , N, 1, \dots , b$ on juhtme poolt kaetud. Paneme tähele, et kui $a=b$, siis katab kaar ainult üht lõiku.

Väljund

Väljundisse kirjutada üks rida $M$ tähemärgiga, millest igaüks on 0 või 1. Tähemärk number $i$ peaks olema 0, kui sisendi kaar number $i$ peaks olema päripäeva elektrivooluga ja 1, kui kaar peaks olema vastupäeva vooluga. Kui leidub mitu lahendust, väljastada ükskõik milline neist.

Kui kaartele pole võimalik vajalikul viisil suundasid anda, väljastada “impossible”.

Piirangud

Selles ülesandes on testid jagatud gruppidesse. Iga grupi eest saavad punkte ainult need programmid, mis lahendavad õigesti kõik gruppi kuuluvad testid. Sinu lõplik skoor on esitatud lahenduste skooride maksimum.

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