10534 - 巨大的牛棚
农夫约翰想要在他的正方形农场上建造一座正方形大牛棚。他讨厌在他的农场中砍树，想找一个能够让他在空旷无树的地方修建牛棚的地方。我们假定，他的农场划分成 N x N 的方格。输入数据中包括有树的方格的列表。你的任务是计算并输出，在他的农场中，不需要砍树却能够修建的最大正方形牛棚。牛棚的边必须和水平轴或者垂直轴平行。
EXAMPLE 考虑下面的方格，它表示农夫约翰的农场，‘.'表示没有树的方格，‘#'表示有树的方格
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
最大的牛棚是 5 x 5 的，可以建造在方格右下角的两个位置其中一个。
输入
Line 1: 两个整数： N （1 <= N <= 1000），农场的大小，和 T （1 <= T <= 10，000）有树的方格的数量
Lines 2..T+1: 两个整数（1 <= 整数 <= N), 有树格子的横纵坐标
输出
输出文件只由一行组成，约翰的牛棚的最大边长。
样例
输入
8 3 2 2 2 6 6 3
输出
5
提示
Big Barn
A Special Treat Farmer John wants to place a big square barn on his square farm. He hates to cut down trees on his farm and wants to find a location for his barn that enables him to build it only on land that is already clear of trees. For our purposes, his land is divided into N x N parcels. The input contains a list of parcels that contain trees. Your job is to determine and report the largest possible square barn that can be placed on his land without having to clear away trees. The barn sides must be parallel to the horizontal or vertical axis.
EXAMPLE
Consider the following grid of Farmer John's land where .' represents a parcel with no trees and #' represents a parcel with trees:
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . # . . . # . .
3 . . . . . . . .
4 . . . . . . . .
5 . . . . . . . .
6 . . # . . . . .
7 . . . . . . . .
8 . . . . . . . .
The largest barn is 5 x 5 and can be placed in either of two locations in the lower right part of the grid.
PROGRAM NAME: bigbrn
INPUT FORMAT
Line 1: Two integers: N (1 <= N <= 1000), the number of parcels on a side, and T (1 <= T <= 10,000) the number of parcels with trees
Lines 2..T+1: Two integers (1 <= each integer <= N), the row and column of a tree parcel
SAMPLE INPUT (file bigbrn.in) 8 3 2 2 2 6 6 3
OUTPUT FORMAT The output file should consist of exactly one line, the maximum side length of John's barn.
SAMPLE OUTPUT (file bigbrn.out) 5