分数: 300 点
问题陈述
有一个网格 N 行和 N 列。 让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。 最初,网格上没有放置任何内容。
您现在将执行 M 操作。的 i第次操作 (1\leq i\leq M) 如下:
- 放置一个占据 2 \times 2 包含单元格的区域 当且仅当其位置不与已放置的任何其他块重叠时, (R_i,C_i) 作为网格的左上角。 更准确地说,对于一组单元格 S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace,如果网格上已经放置了一个块,该块占据了 S,什么也不做; 否则,放置一个占据所有四个单元格的块 S.
执行完所有操作后,找出网格上放置了多少块。
约束
- 2\leq N \leq 10^9
- 1\leq M \leq 2\times 10^5
- 1\leq R_i,C_i \leq N-1
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M R_1 C_1 R_2 C_2 \vdots R_M C_M
输出
打印答案。
示例输入 1
4 3 1 1 2 2 2 3
示例输出 1
2
下图展示了操作过程,其中黑框区域代表块,红框区域代表下一个块要放置的位置。

- 操作 1: 中没有放置任何内容 2 \times 2 包含单元格的区域 当且仅当其位置不与已放置的任何其他块重叠时, (1,1) 作为左上角,所以在那里放置一个块。
- 操作 2:其中 2 \times 2 包含单元格的区域 当且仅当其位置不与已放置的任何其他块重叠时, (2,2) 作为左上角,单元格上已经有另一个块 (2,2),所以什么也不做。
- 操作 3: 中没有放置任何内容 2 \times 2 包含单元格的区域 当且仅当其位置不与已放置的任何其他块重叠时, (2,3) 作为左上角,所以在那里放置一个块。
因此,在执行所有操作之后,两个块被放置在网格上。
示例输入 2
1000000000 4 1 1 1 101 101 1 101 101
示例输出 2
4
块可以放置在所有操作中。
示例输入 3
8 10 6 5 7 3 6 7 3 4 4 2 3 7 1 3 7 4 6 1 6 1
示例输出 3
8
可能存在 i,j\ (i\neq j) 这样 (R_i,C_i)=(R_j,C_j).