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 -264 days 4:03:43

Time elapsed

5:00:00

Time remaining

0:00:00

Problem A
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?

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

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.

Input

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.

Output

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

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$

Ingen vajer har $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