동방 프로젝트 (Large)

동아리방을 가지고 싶었던 병찬이는 사업단에 문의해 N개의 방 중 하나를 얻을 기회를 잡았다. 건물은 일자로 되어 있고, N개의 방이 일직선 위에 나란히 놓여 있다. 맨 왼쪽 방이 1번이고 오른쪽으로 갈수록 번호가 1씩 커져서 맨 오른쪽 방이 N번이다. 이웃한 두 방 사이에는 방을 구분하는 벽이 하나씩 있다.

병찬이 말고도 동아리방을 원하는 사람이 많았지만 방이 충분했기에 병찬이는 안심하고 있었다. 그때 빅종빈 빌런이 나타나 건물의 벽을 허물기 시작했다. 빅종빈 빌런은 다음 규칙으로 벽을 허문다.

• $x < y$인 두 방을 고른 뒤, $x$번 방부터 $y$번 방 사이에 있는 벽을 모두 허문다.
• 두 방 사이의 벽이 허물어지면 두 방은 하나의 방으로 합쳐진다.
• 이미 허물어진 벽은 무시하고 넘어간다.
• 건물이 무너지는 것은 원하지 않으므로 1번 방의 왼쪽 벽과 $N$번 방의 오른쪽 벽, 즉 바깥과 맞닿은 벽은 허물지 않는다.

남은 동아리방이 점점 줄어들자 병찬이는 초조해졌다. 방의 개수 $N$과 빅종빈 빌런의 행동 횟수 $M$이 주어질 때, 모든 행동이 끝난 뒤 남아 있는 동아리방의 수를 구하자.

첫째 줄에 동아리방의 개수를 나타내는 양의 정수 $N$($2 \le N \le 1000000$)이 주어진다. 둘째 줄에 빅종빈 빌런의 행동 횟수를 나타내는 음이 아닌 정수 $M$($0 \le M \le 5000$)이 주어진다. 셋째 줄부터 $M$개의 줄에 각 행동이 양의 정수 $x$, $y$($1 \le x < y \le N$)로 주어진다. 한 행동은 $x$번 방부터 $y$번 방 사이의 벽을 모두 허무는 것을 뜻한다.

빅종빈 빌런은 매우 허당이라서 같은 행동을 여러 번 할 수 있다.

모든 행동이 끝난 뒤 남아 있는 동아리방의 개수를 한 줄에 출력한다.

$N = 5$이고 행동이 $(1, 2)$, $(2, 4)$ 순서로 주어졌다고 하자. 첫 번째 행동으로 1번 방과 2번 방이 합쳐져서 방의 구성은 $(1, 2)$, $(3)$, $(4)$, $(5)$가 된다. 두 번째 행동으로 2번, 3번, 4번 방이 합쳐져서 $(1, 2, 3, 4)$, $(5)$가 된다. 그래서 남아 있는 동아리방은 2개다.