Problem G
Prąd przemienny

Ferdynand bawi się w domu swoją zrobioną na zamówienie kolejką, która napełnia go wielką dumą. Tor kolejki podzielony jest na $N$ segmentów połączonych w kółko, ponumerowanych $1, 2, \dots , N$ w kolejności zgodnej ze wskazówkami zegara. Segmenty są zasilane prądem za pomocą $M$ przewodów poprowadzonych wzdłuż toru. Wzdłuż każdego segmentu biegnie co najmniej jeden przewód.

Ferdynanda zaczął nudzić pociąg, który nie robi nic więcej poza jeżdżeniem w kółko, więc postanowił do każdego segmentu dodać przełącznik zmieniający kierunek jazdy, aby móc aranżować wypadki i inne nieco bardziej ekscytujące scenariusze. Jednak takie przełączniki też wymagają prądu. I to nie byle jakiego – musi to być prąd przemienny. ¹

Ferdynand wymyślił, że doskonałą metodą uzyskania prądu przemiennego będzie podłączenie przełącznika do dwóch źródeł prądu płynącego w przeciwnych kierunkach. Każdy przewód przewodzi prąd wyłącznie w jedną stronę (zgodnie lub przeciwnie do wskazówek zegara), lecz Ferdynand może wybrać w którą. Postanowił więc tak podobierać kierunki prądu w poszczególnych przewodach, aby wzdłuż każdego segmentu biegł przewód przewodzący prąd zgodnie ze wskazówkami zegara oraz przewód przewodzący w przeciwnym kierunku.

Potrafisz pomóc mu w tym zadaniu?

Rozwiązanie pierwszego testu przykładowego. Strzałki na zewnątrz toru przedstawiają przewody. Kierunek i kolor strzałek oznacza kierunek, w którym dany przewód przewodzi prąd. Odwracając kierunki wszystkich strzałek również uzyskamy poprawne rozwiązanie: 11010.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite $N$ i $M$ oznaczające odpowiednio liczbę segmentów toru i liczbę przewodów. Każdy z następnych $M$ wierszy zawiera dwie liczby całkowite $1 \le a, b \le N$ oznaczające przewód biegnący przez segmenty $a, a+1, \dots , b$. Jeśli $b$ jest mniejsze niż $a$ oznacza to, że przewód biegnie przez segmenty $a, \dots , N, 1, \dots , b$. W przypadku $a=b$ przewód pokrywa tylko jeden segment.

Wyjście

Na wyjście wypisz pojedynczy wiersz zawierający $M$ znaków 0 lub 1. $i$-ty znak oznacza kierunek prądu płynącego przez $i$-ty przewód z wejścia – $0$ oznacza kierunek zgodny ze wskazówkami zegara, $1$ przeciwny. W przypadku wielu możliwych rozwiązań wypisz dowolne z nich.

Jeśli nie da się tak pokierować prądu w przewodach, aby przez każdy segment biegł prąd w obu kierunkach, wypisz ,,impossible”.

Ograniczenia

Zestaw testów dzieli się na kilka grup, każda jest warta pewną liczbę punktów. Każda grupa składa się z jednego bądź większej liczby testów. Aby otrzymać punkty za daną grupę, Twoje rozwiązanie musi przejść wszystkie testy z tej grupy. Ostateczny wynik za zadanie jest liczony jako maksymalny wynik z pojedynczych zgłoszeń.

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