아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

감시 카메라

면접 대비

시간 제한4초메모리 제한512 MB

요약
원 위에 놓인 N개 방을 모두 감시하는 카메라 최소 개수를 구하고 불가능하면 impossible을 출력합니다.
난이도

보통10점 중 6점

유형
그리디, 구간, 정렬
정답자
아직 제출이 없습니다

문제

N개의 방이 원형으로 배열되어 있고, K개의 감시 카메라가 각각 연속된 구간(원형으로 넘어갈 수 있음)을 감시합니다. ai≤bia_i \le b_i이면 aia_i부터 bib_i까지, ai>bia_i > b_i이면 bib_i까지와 aia_i부터 N까지를 감시합니다.

모든 방을 감시하는 데 필요한 카메라 개수의 최솟값을 구하세요. 불가능하면 impossible을 출력합니다.

입력

  • 1번째 줄: NN, KK (3≤N≤1063 \le N \le 10^6, 1≤K≤1061 \le K \le 10^6).
  • 다음 KK줄: aia_i, bib_i.

출력

필요한 최소 카메라 수, 또는 impossible.

예제5

  1. 예제 1

    입력
    100 7
1 50
50 70
70 90
90 40
20 60
60 80
80 20
    예상 출력
    3

  2. 예제 2

    입력
    5 3
1 3
2 4
4 2
    예상 출력
    2

  3. 예제 3

    입력
    8 2
1 8
3 6
    예상 출력
    1

  4. 예제 4

    입력
    20 5
5 8
9 12
16 5
16 4
7 10
    예상 출력
    impossible

  5. 예제 5

    입력
    30 6
28 1
3 7
12 17
24 7
28 5
9 21
    예상 출력
    impossible