문제
N×M크기의 격자칸이 있다. 가장 왼쪽 위 칸을 (1, 1), 가장 오른쪽 아래 칸을 (N, M)이라고 하자.
격자칸의 제일 아래 행 바로 밑에는 물이 투과하지 못하는 바닥이 있다고 한다.
격자칸의 각 칸들은 막혀 있거나, 뚫려 있다. 막혀 있는 칸은 물이 투과하지 못한다.
한 열을 보면 막혀 있는 칸이 없거나, 막혀있는 칸들이 하나의 덩어리로 연속하여 나타난다.
인접한 막혀 있는 칸들 사이로 물이 투과하지 못한다.
한 열에 있는 덩어리가 가장 아래 행에 있는 칸을 포함할 때 이 덩어리를 바닥에 붙은 덩어리라고 부른다.
바닥에 붙은 덩어리가 아닌 덩어리는 공중에 뜬 덩어리라고 부른다.
인접한 열에 있는 두 덩어리를 보았을 때, 두 덩어리가 같은 행에 있는 칸을 포함하면 두 덩어리는 붙어서 한 덩어리가 된다.
이렇게 붙은 세로 경계로도 물은 투과하지 못한다. 이렇게 붙는 과정은 연속한 열에 모두 적용된다.
아래 그림의 두 번째와 세 번째 열처럼 바닥에 붙은 덩어리와 공중에 뜬 덩어리가 붙어야 하는 경우는 주어지지 않는다.
즉, 인접한 열에 있는 덩어리들이 붙는 경우는 둘 다 바닥에 붙은 경우이거나 둘 다 공중에 뜬 경우이다.
또, 아래 그림의 다섯 번째와 여섯 번째 열처럼 두 덩어리가 꼭지점 하나에서만 만나는 경우도 주어지지 않는다.
예를 들어, 아래 그림의 예를 보면 8×12 크기의 격자칸이 있다. 이 격자칸의 첫 번째 열에는 6번째 칸부터 8번째 칸까지 막혀 있고, 두 번째 열은 막혀 있는 칸이 없으며, 세 번째 열은 5번째 칸부터 8번째 칸까지 막혀 있다는 것을 알 수 있다.
이 격자칸에 위에서 물을 충분히 부었다고 하자. 1번으로 표시된 칸들에는 물이 고임을 쉽게 알 수 있다.
2번으로 표시된 칸들도 마찬가지이다. 3번과 4번으로 표시된 칸들에도 물이 고인다. 이 부분은 주의할 필요가 있다.
이 문제에서는 공기가 없다고 생각하기 때문에 4번 부분에도 3번 부분과 같은 높이까지 물이 고인다.
(공기는 모든 것을 투과한다고 생각해도 마찬가지이다.)
5번 부분에는 공중에 뜬 덩어리 위에 물이 고인 경우이다.
6번 부분과 같은 경우에는 물이 고이지 않음에 주의하라.
칸들의 배치를 입력으로 받아 물을 충분히 부었을 때 물이 고이는 칸들의 개수를 출력하는 프로그램을 작성하라.
입력
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 두 정수 N, M이 주어진다. ( 1 ≤ N, M ≤ 100,000 ).
다음 M개의 줄에는 두 정수 A, B가 주어진다. (1 ≤ A ≤ B ≤ N) 이는 왼쪽에서 오른쪽으로 차례대로,
해당하는 열에 막힌 칸의 위치가 A행부터 B행 까지라는 뜻이다.
특수한 경우로, 해당하는 열에 막힌 칸이 없으면 A, B 모두 0으로 주어진다.
출력
표준 출력으로 주어진 격자에서 물을 충분히 부었을 때 물이 고이는 칸들의 개수를 출력한다.
[부분문제의 제약 조건]
* 부분문제 1: 전체 점수 100점 중 7점에 해당하며 막힌 칸은 맨 첫 열과 맨 마지막 열에만 있다.
* 부분문제 2: 전체 점수 100점 중 18점에 해당하며 어떤 열에 막힌 칸이 있다면, 반드시 바닥에 붙어 있다.
* 부분문제 3: 전체 점수 100점 중 28점에 해당하며 1 ≤ N, M ≤ 1,000 .
* 부분문제 4: 전체 점수 100점 중 47점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.
예제1
8 12
6 8
0 0
5 8
7 8
5 8
0 0
1 6
2 2
1 6
0 0
5 8
0 0
22
예제2
15 35
11 15
0 0
0 0
0 0
15 15
7 13
3 10
1 10
1 13
2 6
11 15
10 15
8 15
6 15
9 15
5 6
1 10
9 11
1 12
4 4
9 15
13 15
0 0
8 15
13 15
10 10
3 12
4 6
1 9
9 11
13 15
10 15
0 0
0 0
11 15
130
예제3
14 12
8 14
0 0
0 0
6 14
1 4
2 2
1 7
5 7
9 14
4 14
5 14
10 14
50