교대 전류

프레드릭은 원형으로 연결된 $N$개의 구간으로 이루어진 모형 철도를 가지고 있다. 구간에는 시계 방향 순서대로 $1, 2, \dots, N$ 번호가 붙어 있다. 열차에 전기를 공급하기 위해 원을 따라 휘어진 $M$개의 전선이 설치되어 있으며, 모든 구간에는 최소 하나의 전선이 지나간다.

프레드릭은 모든 구간에 전환기를 설치하려 한다. 전환기에는 교류 전원이 필요하다. Fredrik의 생각에 교류란 양쪽 방향으로 전류가 흐르는 것이다. 각 전선은 한 방향, 시계 방향 또는 반시계 방향으로만 전류를 흘릴 수 있으며, Fredrik은 각 전선의 방향을 자유롭게 정할 수 있다. 모든 구간이 시계 방향 전류를 흘리는 전선과 반시계 방향 전류를 흘리는 전선에 각각 최소 하나씩 덮이도록 전선의 방향을 정해야 한다.

가능하다면 그러한 방향 선택을 하나 찾아라.

위 그림은 첫 번째 예시에 대한 해를 나타낸다. 철도 바깥의 곡선 화살표가 전선을 나타내며, 화살표 방향이 Fredrik이 정한 전류 방향이다. 모든 화살표를 뒤집으면 또 다른 유효한 해가 된다.

스웨덴 철도에서는 모든 분기기(스웨덴어로 växlar)가 교류(스웨덴어로 växelström)를 사용하기 때문에 이러한 발상이 타당하다.

첫째 줄에 철도 구간의 수 $N$과 전선의 수 $M$이 주어진다.

다음 $M$줄에는 각 전선을 나타내는 두 정수 $a$와 $b$가 주어진다. 단, $1 \le a, b \le N$이다. 이 전선은 구간 $a, a+1, \dots, b$를 덮는다. $b$가 $a$보다 작으면 원 위에서 감기며 구간 $a, \dots, N, 1, \dots, b$를 덮는다는 뜻이다. $a = b$이면 해당 구간 하나만 덮는다.

길이가 $M$인 한 줄을 출력한다. $i$번째 문자는 $i$번째 전선의 전류를 시계 방향으로 흘릴 경우 $0$, 반시계 방향으로 흘릴 경우 $1$이다. 해가 여러 개이면 그중 아무거나 출력한다.

유효한 해가 없으면 impossible를 출력한다.