Baltic Olympiad in Informatics 2018 Open - day 2

Start

2018-04-29 07:30 UTC

Baltic Olympiad in Informatics 2018 Open - day 2

End

2018-04-29 12:30 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -300 days 1:07:57

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
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. 1

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?

\includegraphics[width=0.5\textwidth ]{alternatingfig.pdf}

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.

Input

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.

Output

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”.

Constraints

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group. Your final score will be the maximum score of a single submission.

Group

Points

Limits

Additional Constraints

1

13

$2 \le N, M \le 15$

 

2

20

$2 \le N, M \le 100$

 

3

22

$2 \le N, M \le 1000$

 

4

19

$2 \le N, M \le 100\, 000$

Ühegi kaare puhul ei ole $b < a$.

5

26

$2 \le N, M \le 100\, 000$

 
Sample Input 1 Sample Output 1
10 5
1 5
6 7
5 1
7 2
2 4
00101
Sample Input 2 Sample Output 2
10 5
1 4
2 5
4 7
6 10
8 1
impossible
Sample Input 3 Sample Output 3
5 2
1 5
3 3
impossible
Sample Input 4 Sample Output 4
5 3
3 3
2 1
4 2
101

Footnotes

  1. Seda sellepärast, et rootsi keeles on raudteepööre (“växlar”) ja vahelduvvool (“växelström”).