문제
도영이는 정올광역시 외곽에 설치된 순환철도를 운행하고 있다.
순환철도는 원형으로 이루어져 있고, 전기로 작동한다.
이 철도는 10m단위로 공장에서 생산된 “부분” 철도(편의상 조각이라고 부르자) N개가
시계 방향으로 연결되어 있는 형태로 이루어져 있다.
이 중 조각 하나를 1번이라고 한다면, 시계 방향으로 2번, 3번,…N번 조각이 된다.
그림 1. N=10인 철도망의 예
현재 이 순환철도 노선에는 M개의 전선망이 있는데,
한 전선망은 조각 si번부터 시작해서 시계 방향으로 조각 ei번까지 직류 전류를 공급하고 있다.
이 직류 전류가 흐르는 방향은 시계 방향이다.
현재 모든 철도망에 전기가 들어오므로, 어떤 철도 조각이든 적어도 한 전선망에서는 전류 공급을 받는다.
도영이는 승객들의 안전을 위하여 전류 공급 방식을 교류로 바꾸려고 하는데,
물리학을 무시하고 기적의 논리를 펼쳐, 다음과 같은 방식으로 교류 전류를 만들려고 한다.
- 현재 시계 방향으로 흐르고 있는 전선망 몇 개의 방향을 반시계방향으로 바꾼다.
- 어떤 철도 조각에 시계 방향으로 흐르는 직류 전류와, 반시계 방향으로 흐르는 직류 전류가 동시에 흐른다면, 교류 전류가 된다(?!?!?)
도영이는 모든 철도 조각에 교류 전류가 흐르게 하고 싶다.
그렇게 하기 위해 각 전선망별로 어느 방향으로 전류를 흘려야 하는지 정해주는 프로그램을 작성하시오.
입력
첫 줄에 N과 M이 주어진다. N은 철도 조각의 개수이고, M은 전선망의 개수이다.
다음 M 줄에 걸쳐서 전선망의 정보인 si, ei가 주어진다.
이는 해당 전선망이 si번 철도 조각부터 시작해서 시계 방향으로 ei번 철도 조각까지 전기를 공급하고 있음을 뜻한다.
만약 si= ei이면, si(ei)번 조각 하나만 전기가 통함을 뜻한다.
부분문제의 제약 형식
모든 부분문제에서 2≤N,M≤100,000 , 1≤si,ei≤N이다.
부분문제 1) (13점) N,M≤15을 만족한다.
부분문제 2) (20점) N,M≤100을 만족한다.
부분문제 3) (22점) N,M≤1,000을 만족한다.
부분문제 4) (19점) 모든 전선망에 대해 si≤ ei이다
부분문제 5) (26점) 주어진 제약 조건 외에 아무 제약조건이 없다.
출력
첫 줄에 0과 1로만 이루어진 길이 M의 문자열을 출력한다.
i번 전선망이 시계 방향으로 전류를 흘러야 한다면 i번째 문자에 0을 출력,
반시계 방향이라면 1을 출력한다.
가능한 정답이 여러 개가 있다면, 그 중 아무거나 하나를 출력한다.
만약 전 구간에 교류 전류를 만드는 것이 불가능하다면, 첫 줄에 impossible을 출력한다.
예제1
105
15
67
51
72
24
00101
예제2
105
14
25
47
610
81
impossible