ENDLESS RAIN

고려대학교는 특이하게 매일 첫 번째 수업을 시작할 때부터 마지막 수업이 끝날 때까지 비가 온다고 한다. 비 맞는 것을 싫어하는 근호는 학교 건물을 연결하는 길목들에 거대한 파라솔을 설치하여 비를 피하려고 한다.

고려대학교는 아래와 같이 $N$개의 건물이 일렬로 배치된 형태이다. 왼쪽에 있는 건물부터 순서대로 $1$번 건물, $2$번 건물, $\cdots$, $N$번 건물이고, 인접한 건물 사이에는 두 건물을 직접 연결하는 길목이 있다. 파라솔은 각 길목당 하나씩 설치할 수 있으며, 파라솔이 설치된 길목은 지나갈 때 비를 맞지 않는다.

근호는 한 학기 동안 고려대학교에서 수업을 들을 것이다. 한 학기는 $M$일이고, $i(1\leq i\leq M)$번째 날에는 $A_i$번 건물부터 $B_i$번 건물 사이에 있는 건물들에서 수업을 듣는다. 근호가 $i$번째 날에 비를 맞지 않으려면 $i$번째 날 수업을 듣기 전에 $A_i$번 건물과 $B_i$번 건물 사이에 있는 모든 길목에 파라솔이 설치되어 있어야 한다.

그래서 근호는 학기 중 매일 아침, 등교해서 수업을 듣기 전에 원하는 길목에 파라솔을 설치하기로 했다. 파라솔을 설치하는 데는 시간이 걸리기 때문에, 매일 아침에 설치할 수 있는 파라솔의 개수는 최대 $1$개이다.

하지만 근호는 매일 아침에 파라솔을 설치하는 것만으로는 수업 시간표에 맞춰 파라솔을 모두 설치할 수 없을 것임을 깨닫고, 학기가 시작되기 전에 미리 파라솔을 몇 개 설치하려고 한다.

근호가 한 학기 동안 비를 한 번도 맞지 않으려면 학기가 시작되기 전에 최소 몇 개의 길목에 파라솔을 미리 설치해야 하는가? 처음에는 모든 길목에 파라솔이 설치되어 있지 않고, 한 번 설치한 파라솔은 학기가 끝날 때까지 설치된 상태를 유지한다.

첫 번째 줄에 고려대학교의 건물 개수 $N$과 한 학기의 일 수 $M$이 공백으로 구분되어 정수로 주어진다. ($1\leq N\leq 500\,000;$ $1\leq M\leq 1\,000\,000$)

이후 $M$개의 줄에 걸쳐 근호의 수업 시간표가 주어진다. $i+1$번째 줄에는 정수 $A_i$, $B_i$가 주어진다. ($1\leq A_i\leq B_i\leq N$)

입력되는 데이터의 양이 많음에 유의하자.

첫 번째 줄에 근호가 개강 전에 파라솔을 설치해야 하는 길목의 최소 개수를 출력한다.