레이팅 미적용International Corporation for Protection and Control(ICPC)은 말 그대로 보호와 통제를 위한 효율적인 기술을 개발한다. 당연히 이들은 자신들의 본사도 보호하고 통제하고 싶어 한다. 위에서 내려다보면 본사 건물은 볼록 다각형 모양이다. 건물 주위에는 건물을 감시할 카메라를 설치할 수 있는 적당한 장소가 여러 곳 있다. 각 카메라는 위치에 따라 다각형 변들(건물 벽들)의 특정 구간을 커버한다. ICPC는 건물 전체를 커버하는 데 필요한 카메라 수를 최소화하고 싶어 한다.
입력은 하나의 테스트 케이스로 이루어져 있다. 첫 줄에는 두 정수 \(n\)과 \(k\) (\(3 \le n \le 10^{6}\), \(1 \le k \le 10^{6}\))가 주어지며, \(n\)은 벽의 수이고 \(k\)는 카메라를 설치할 수 있는 장소의 수이다. 나머지 \(k\)개의 줄에는 각각 두 정수 \(a_{i}\)와 \(b_{i}\) (\(1 \le a_{i}\), \(b_{i} \le n\))가 주어진다. 이 정수들은 \(i^{th}\)번째 장소의 카메라가 어느 벽들을 커버하는지 지정한다. \(ai \le bi\)이면 카메라는 \(ai \le j \le bi\)인 각 벽 \(j\)를 커버한다. \(ai > bi\)이면 카메라는 \(ai \le j \le n\) 또는 \(1 \le j \le bi\)인 각 벽 \(j\)를 커버한다.
건물의 모든 벽을 커버하기에 충분한 최소 카메라 수를 출력한다. 두 카메라가 커버하는 구간은 겹쳐도 된다. 건물을 커버할 수 없으면 대신 impossible을 출력한다.
100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20
3
8 2
8 3
5 7
impossible
8 2
8 4
5 7
2