시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 150 27 17 19.318%

문제

홍준이는 한국에서 손에 꼽히는 부자 중 한 명이다. 홍준이의 집은 N개의 방이 원형으로 나열된 형식으로 구성되어 있다. 홍준이는 자신의 집에 K개의 감시 카메라를 설치했다. 각 감시 카메라는 원형으로 나열된 방들 중 일부 연속된 구간을 감시한다. 홍준이는 모든 방을 다 감시하고 싶어 하는데, 이미 설치된 K개의 감시 카메라 중 몇 개는 필요하지 않다는 것을 깨달았다.

홍준이의 방은 1번 방부터 N번 방까지 원형으로 배열되어 있다. 즉, 1번 방 양 옆에는 2번 방과 N번 방이 있고, N번 방 양 옆에는 N-1번 방과 1번 방이 있다.

K개의 감시 카메라가 감시하는 구간에 대한 정보가 주어졌을 때, 모든 방을 감시하기 위해 필요한 최소 감시 카메라 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 방의 개수 N과 감시 카메라의 개수 K가 주어진다. (3 ≤ N ≤ 106, 1 ≤ K ≤ 106)

다음 K개의 줄에 각 감시 카메라에 대한 정보 ai와 bi가 주어진다. (1 ≤ ai, bi, ≤ N)

ai ≤ bi 인 경우, ai ≤ j ≤ bi 를 만족하는 j번 방이 감시 받는다는 것을 의미하고, ai > bi 인 경우, 1 ≤ j ≤ bi 혹은 ai ≤ j ≤ N 을 만족하는 j번 방이 감시 받는다는 것을 의미한다.

출력

홍준이가 모든 방을 감시하기 위해 필요한 감시 카메라의 최소 개수를 출력한다. 만약, 모든 방을 감시하는 것이 불가능하다면,  impossible을 출력한다.

예제 입력

100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20

예제 출력

3

힌트

출처

ACM-ICPC > World Finals > 2014 World Finals K번