CF203B.Game on Paper

One not particularly beautiful evening Valera got very bored. To amuse himself a little bit, he found the following game.

He took a checkered white square piece of paper, consisting of n × n cells. After that, he started to paint the white cells black one after the other. In total he painted m different cells on the piece of paper. Since Valera was keen on everything square, he wondered, how many moves (i.e. times the boy paints a square black) he should make till a black square with side 3 can be found on the piece of paper. But Valera does not know the answer to this question, so he asks you to help him.

Your task is to find the minimum number of moves, till the checkered piece of paper has at least one black square with side of 3. Otherwise determine that such move does not exist.

一个并不特别美好的傍晚，瓦莱拉感到非常无聊。为了稍微娱乐一下自己，他找到了下面这个游戏。

他取了一张由 $n \times n$ 个方格组成的白色方格纸。接着，他开始逐个将白色方格涂成黑色。总共他在纸上涂黑了 $m$ 个不同的方格。由于瓦莱拉对一切正方形都情有独钟，他不禁思考：至少需要多少次涂色操作（即每次将一个方格涂黑），才能使得纸上首次出现一个边长为 3 的黑色正方形？但瓦莱拉并不知道这个问题的答案，因此他请你来帮忙。

你的任务是找出使得纸上至少出现一个边长为 3 的黑色正方形所需的最小涂色次数；若无论如何涂色都无法形成这样的正方形，则判定该操作不存在。

The first line contains two integers n and m (1 ≤ n ≤ 1000, 1 ≤ m ≤ min(n·n, 105)) — the size of the squared piece of paper and the number of moves, correspondingly.

Then, m lines contain the description of the moves. The i-th line contains two integers x__i, y__i (1 ≤ x__i, y__i ≤ n) — the number of row and column of the square that gets painted on the i-th move.

All numbers on the lines are separated by single spaces. It is guaranteed that all moves are different. The moves are numbered starting from 1 in the order, in which they are given in the input. The columns of the squared piece of paper are numbered starting from 1, from the left to the right. The rows of the squared piece of paper are numbered starting from 1, from top to bottom.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 1000$，$1 \leq m \leq \min(n \cdot n,\, 10^5)$），分别表示正方形纸张的尺寸和操作次数。

接下来 $m$ 行描述每次操作。第 $i$ 行包含两个整数 $x_i$、$y_i$（$1 \leq x_i, y_i \leq n$），表示第 $i$ 次操作中被涂色的方格所在的行号与列号。

每行中的所有数字均以单个空格分隔。保证所有操作互不相同。操作按输入中给出的顺序从 $1$ 开始编号。正方形纸张的列号从左至右依次编号，起始为 $1$；行号从上至下依次编号，起始为 $1$。

On a single line print the answer to the problem — the minimum number of the move after which the piece of paper has a black square with side 3. If no such move exists, print -1.

在一行中输出该问题的答案——即纸张上首次出现边长为 3 的黑色正方形时的最小移动步数。若不存在这样的移动步数，则输出 -1。