一个不是特别美丽的夜晚,瓦莱拉感到非常无聊。为了自娱自乐,他找到了下面的游戏。
他拿了一张白色方格纸,由 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