문제
국제보호통제연합은 보호 및 통제를 위하여 효율적인 기술을 개발한다. 당연히 자신들의 본부가 보호와 통제가 잘 되기를 바란다.
국제보호통제연합의 본부건물은 볼록다각형모양으로 외벽의 각각은 1에서 N까지 번호가 붙어 있다. 건물을 감시할 수 있도록 건물 외부에 카메라를 설치하려고 한다. 각 카메라는 설치된 위치에 따라 다각형의 일정 부분을 감시할 수 있다고 한다.
비용 문제로 국제보호통제연합은 본부에 설치할 카메라의 대수를 최소로 하고자 한다.
입력
첫 행에 건물 외벽의 개수 N(3 ≤ N ≤ 106)과 카메라의 대수 K( 1 ≤ K ≤ 106)가 입력된다.
다음 행부터 K개의 행에 걸쳐 각 카메라를 설치할 경우 감시가 가능한 벽의 시작번호와
마지막 번호 ai, bi ( 1 ≤ ai, bi ≤ N 의 정수)가 공백으로 구분되어 주어진다.
ai ≤ bi 인 경우 감시 가능한 벽 번호 j는 ai ≤ j ≤ bi이다.
ai > bi인 경우 감시 가능한 벽 번호 j는 ai ≤ j ≤ N 과 1 ≤ j ≤ bi 가 된다.
출력
건물 벽 전체를 감시 할 때 필요한 최소 개수의 카메라 수를 출력한다.
건물 벽 전체를 감시할 수 없는 경우 impossible을 출력한다.
예제 #1
100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20
3
예제 #2
8 2
8 3
5 7
impossible
예제 #3
8 2
8 4
5 7
2
출처
ACM-ICPC 2014 world finals K
로그인해야 코드를 작성할 수 있어요.