B. Игра на листочке
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В один не самый прекрасный вечер Валере было очень скучно. Чтобы немного себя развлечь, Валера нашел следующее занятие.

Он взял белый квадратный клетчатый лист бумаги, состоящий из 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.

Примеры
Входные данные
4 11
1 1
1 2
1 3
2 2
2 3
1 4
2 4
3 4
3 2
3 3
4 1
Выходные данные
10
Входные данные
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
Выходные данные
-1