AT_abc203_e [ABC203E] White Pawn

设 $N$ 为正整数。有一个 $(2N+1)\times (2N+1)$ 的棋盘，行和列的编号分别为 $0$ 到 $2N$，位于第 $i$ 行第 $j$ 列的格子记作 $(i,j)$。 棋盘上有一个白色兵，最初放在 $(0,N)$。有 $M$ 个黑色兵，第 $i$ 个黑色兵放在 $(X_i, Y_i)$。 当白色兵在 $(i,j)$ 时，你可以通过以下任一操作移动白色兵： - 若 $0\leq i\leq 2N-1$，$0\leq j\leq 2N$，且 $(i+1,j)$ 没有黑色兵，则可以将白色兵移动到 $(i+1,j)$。 - 若 $0\leq i\leq 2N-1$，$0\leq j\leq 2N-1$，且 $(i+1,j+1)$ 有黑色兵，则可以将白色兵移动到 $(i+1,j+1)$。 - 若 $0\leq i\leq 2N-1$，$1\leq j\leq 2N$，且 $(i+1,j-1)$ 有黑色兵，则可以将白色兵移动到 $(i+1,j-1)$。 黑色兵不能移动。 请你求出，经过若干次操作后，白色兵最终可以到达 $(2N,Y)$ 的不同 $Y$ 的个数。

输入通过标准输入给出，格式如下： > $N$ $M$ $X_1$ $Y_1$ $:$ $X_M$ $Y_M$

输出答案。

## 限制条件 - $1\leq N\leq 10^9$ - $0\leq M\leq 2\times 10^5$ - $1\leq X_i\leq 2N$ - $0\leq Y_i\leq 2N$ - $(X_i, Y_i)\neq (X_j, Y_j)$（$i\neq j$） - 所有输入均为整数。 ## 样例解释 1 可以分别如下移动到 $(4,0)$、$(4,1)$、$(4,2)$ 这三个位置： - $(0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,2)$ - $(0,2)\to (1,1)\to (2,1)\to (3,1)\to (4,1)$ - $(0,2)\to (1,1)\to (2,0)\to (3,0)\to (4,0)$ 另一方面，无法移动到 $(4,3)$ 和 $(4,4)$。因此，输出 $3$。 ## 样例解释 2 无法将白色兵从 $(0,1)$ 移动到其他位置。 由 ChatGPT 4.1 翻译