FJ 有一个大小为 n\times n 的农场（1\le n\le 1000），他想要在他的农场上建造一座正方形大牛棚。他的农场中有 t 棵果树（1\le t\le10000），但他为了不破坏果树，就想找一个空旷无树的地方修建牛棚。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚的边长。当然，牛棚的边必须和水平轴和垂直轴平行。

考虑下面的农场，. 表示没有树的方格，# 表示有树的方格。

0 1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .

最大的牛棚是边长为 5 的，可以建造在农场右下角的两个位置其中一个。

第 1 行输入两个正整数 n 和 t。

第 2\cdots t+1 行输入两个正整数 x,y\ (1\le x,y\le n)。

只由一行组成，约翰的牛棚的最大边长。

提示

USACO Training Section 5.3