Consider an n by n array A of 0 and 1's. We say that there is a hole in A at (x, y) with width d if the value of A[i, j] is 0, where
i = x, (x + 1), (x + 2), . . . , (x + d - 1)
j = y, (y + 1), (y + 2), . . . , (y + d - 1),
and (x + d - 1) < n, (y + d - 1) < n. That is, all values within the "square" at (x, y) with width d are 0's. Note that the indices of the array start from 0.
Given the array A, we want to find the width of the largest hole.
The following figure shows an array where the entry A[i, j] is at the i-th row and j-th column.
In this array, there is a hole of width 3 at (0,0), and it is not possible to have a hole of width 4 at (0,0). The largest hole has width 5 and it is at (1,2), which is highlighted in the figure.
The input represents the input array A. The following is the input for the array shown above.
8 5 3 1 7 0 6 4 0 5 5 7
The first line contains a positive integer n ≤ 1,024 which is the width of the array. The second line contains an integer k, which is the number of 1's in the array. Next, it is followed by k more lines which specify the entries with value 1. Each line contains two integers x and y, which indicates that A[x, y] = 1.
Since the value of n may be as large as 1,024, your program has to run fast enough to handle arrays of that size.
The output file consists of an integer, which is the width of the largest hole. If there is no hole in the array, the output is 0. The following is the output of our example.