Problem G
Двусторонний ток

Фредерик играет с игрушечной железной дорогой, которую он сам сделал, чем очень гордится. Дорога состоит из $N$ сегментов путей, соединённых по кругу, и пронумерованных $1, 2, \dots , N$ по часовой стрелке. Электричество подается локомотиву через $M$ проводов, проложенных арками вдоль круга. Через каждый сегмент дороги проложен как минимум один провод.

Фредерику поднадоел наворачивающий круги поезд, и он решил добавить к каждому сегменту стрелочную развилку, чтобы устраивать поезду аварии и прочим образом злобно развлекаться. Стрелочные развилки, однако, нужно запитать электричеством, причем им подходит только специальный, двусторонний ток.

По каждому проводу, проложенному вдоль путей, ток может течь в одном направлении – либо по часовой, либо против часовой стрелки, причем Фредерик может выбирать направление на своё усмотрение. Двусторонний ток можно получить, если подвести к сегменту ток и в одном, и в другом направлении (по двум разным проводам).

Таким образом, Фредерику нужно придумать, в какую сторону направить ток по каждому проводу, чтобы каждый сегмент путей был бы покрыт как минимум одним проводом с током, текущим по часовой стрелке, и одним проводом с током, текущим против часовой стрелки. Помоги Фредерику решить эту задачу.

Решение первого примера. Стрелки вокруг железной дороги показывают провода, поставляющие электричество. Направление каждой стрелки соответствует выбранному Фредериком направлению тока (синий и красный цвет подчеркивают разные направления). Обратите внимание, что все стрелки можно развернуть, чтобы получить второе корректное решение: 11010.

Ввод

На первой строке даны два целых числа $N$ и $M$ – количество сегментов железной дороги и количество проводов, соответственно.

На каждой из следующих $M$ строк даны два числа $1 \le a, b \le N$, указывающих, что имеется провод, покрывающий сегменты $a, a+1, \dots , b$. Если $b$ меньше $a$, это значит что последовательность сегментов перескакивает через $N$, т.е. покрываются сегменты $a, \dots , N, 1, \dots , b$. Если $a=b$, то провод покрывает только один сегмент.

Вывод

На единственной строке вывести последовательность символов длиной $M$, состоящую из знаков 0 или 1. $i$-тый символ должен быть равен 0, если ток в $i$-том проводе нужно направить по часовой стрелке, и 1, если ток нужно направить против часовой стрелки. Если существует несколько решений, вывести любое из них.

Если решений нет, вывести текст “impossible”.

Ограничения

Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.

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