← 返回题目列表

Codeforces · 203/B

B. 纸上游戏

中文机器翻译题面 查看原题

一个不是特别美丽的夜晚,瓦莱拉感到非常无聊。为了自娱自乐,他找到了下面的游戏。

他拿了一张白色方格纸,由 n × n 个单元格组成。之后,他开始将白色的细胞一个又一个地涂成黑色。他总共在纸上画了 m 个不同的单元格。由于瓦莱拉热衷于一切正方形,他想知道他应该移动多少次(即男孩将正方形涂成黑色),直到在纸上找到边长为 3 的黑色正方形。但瓦莱拉不知道这个问题的答案,所以他请你帮助他。

你的任务是找到最少的移动次数,直到格子纸上至少有一个边长为3的黑色方块。否则确定这样的移动不存在。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 1000, 1 ≤ m ≤ min(n·n, 105)) — 相应的正方形纸的大小和移动次数。

然后,m 行包含移动的描述。第 i 行包含两个整数 xi, yi (1 ≤ xi, yi ≤ n) — 第 i 次移动时绘制的正方形的行数和列数。

行上的所有数字均以单个空格分隔。保证所有动作都是不同的。移动按照输入中给出的顺序从 1 开始编号。正方形纸的各列从 1 开始,从左到右编号。正方形纸的行从 1 开始,从上到下编号。

输出

在一行中打印问题的答案 - 纸片出现边长为 3 的黑色正方形后的最小移动次数。如果不存在这样的移动,则打印 -1。

示例

输入 #1

4 11
1 1
1 2
1 3
2 2
2 3
1 4
2 4
3 4
3 2
3 3
4 1

输出 #1

10

输入 #2

4 12
1 1
1 2
1 3
2 2
2 3
1 4
2 4
3 4
3 2
4 2
4 1
3 1

输出 #2

-1