문제
주식회사 정올에서는 맥시마라고 불리는 새로운 정렬용 하드웨어를 개발하고자 한다. 맥시마란 n개 정수가 입력이 올 때 입력으로 들어온 수 중 가장 큰 숫자를 출력하는 기계이다.
맥시마는 여러 개의 정렬기를 조합해서 구현된다. 정렬기란 S(i, j)로 정의 되는 기계로 맥시마의 i번째 입력부터 j번째 입력까지(i ≤ j)를 숫자를 비-내림차순으로 정렬하고 나머지는 그대로 두어 새로운 입력을 말하는 부품을 말한다.
모든 정렬기를 거친 다음 n번째 입력에 있는 숫자가 맥시마의 출력이 된다.
만약 주어진 입력이 4 3 2 1 이고 S(2, 3), S(2, 4)라는 정렬기가 있을 경우 다음과 같은 형태로 맥시마가 구동 된다.
초기 : 4 3 2 1
S(2,3) 적용 : 4 2 3 1
S(2,4) 적용 : 4 1 2 3
이 경우는 맥시마가 3을 출력하게 된다.
당신은 몇 개의 정렬기를 없앨 경우에도 맥시마가 잘 동작함을 알 수 있었다. 여러 개의 정렬기가 주어졌을 때, 모든 가능한 입력에 대해서 올바른 출력을 내놓기 위해서 사용해야할 정렬기의 최소 개수를 찾는 프로그램을 작성하자.
정렬기의 순서는 반드시 지켜져야 한다. 편의상 맥시마에 들어오는 입력은 n개의 입력이 주어졌을 때 1부터 n까지의 정수가 들어온다고 가정 한다.
입력
입력의 첫 번째 줄에는 맥시마의 입력의 개수 N(1≤N≤50,000)과 맥시마의 정렬기의 개수 M(1≤M≤ 500,000)이 입력된다.
그 다음 줄부터 M개의 줄에는 k번째 정렬기 S(ik jk)의 ik와 jk가 순서대로 입력된다(1≤ik jk≤N).
출력
모든 가능한 입력에 대해서 맥시마가 제대로 동작하기 위한 최소의 정렬기 횟수를 출력한다.
예제
40 6
20 30
1 10
10 20
20 30
15 25
30 40
4
로그인해야 코드를 작성할 수 있어요.