CF203B Game on Paper

在一个并不特别美丽的夜晚，Valera 感到非常无聊。为了给自己找点乐子，他发明了如下的游戏。 他拿出了一张由 $n \times n$ 个格子组成的白色方格纸。接着，他开始逐个把白色格子涂黑。一共涂黑了 $m$ 个不同的格子。由于 Valera 对所有方形的东西都很感兴趣，他想知道，最少需要多少次操作（即涂黑某个格子），才能让纸上出现一个边长为 $3$ 的全黑正方形。不过 Valera 不知道答案，所以他向你寻求帮助。 你的任务是求出最少需要多少步操作后，方格纸上就会出现至少一个边长为 $3$ 的全黑正方形。如果一步也达不到这样的正方形，则输出 -1。

第一行包含两个整数 $n$ 和 $m$，分别表示方格纸的边长和操作次数，其中 $1 \leq n \leq 1000$，$1 \leq m \leq \min(n \cdot n, 10^{5})$。 接下来 $m$ 行，每行包含两个整数 $x_i$、$y_i$，表示在第 $i$ 步操作中，第 $x_i$ 行第 $y_i$ 列的格子被涂黑（$1 \leq x_i, y_i \leq n$）。 所有输入的行中数字用单个空格分隔。保证所有操作互不相同。操作按输入顺序编号，第 $1$ 步编号为 $1$。方格纸的列从左到右编号为 $1$ 到 $n$；行从上到下编号为 $1$ 到 $n$。

输出一个整数，表示操作步数的最小值，在进行了这一步操作后，方格纸上至少出现了一个边长为 $3$ 的全黑正方形。如果一直没有出现这样的正方形，输出 $-1$。

由 ChatGPT 5 翻译