Hole

A group of scientists want to monitor a huge forest. They plan to airdrop small sensors into the forest. Many conditions during the airdrop are unpredictable, so each sensor lands in a random location. After all sensors have landed, square regions that contain no sensor remain in the forest. Call such a region a hole.

Small holes are desirable, and airdropping a very large number of sensors achieves that. Sensors are expensive, though. So the scientists want to run a computer simulation to decide how many sensors to airdrop, so that the chance of a large hole is small. The simulation needs a subroutine that reads the locations of the sensors and outputs the size of the largest hole. The simulation repeats many times with different parameters, so the subroutine has to be fast. Writing that subroutine is your task.

Consider an $n \times n$ array $A$ of 0s and 1s. There is a hole in $A$ at $(x, y)$ with width $d$ when both of the following hold.

• $A[i, j] = 0$ for every $(i, j)$ with $i = x, x+1, x+2, \dots, x+d-1$ and $j = y, y+1, y+2, \dots, y+d-1$.
• $x + d - 1 < n$ and $y + d - 1 < n$.

That is, every value inside the square at $(x, y)$ with width $d$ is 0. The indices of the array start from 0.

Given the array $A$, find the width of the largest hole.

The input represents the array $A$.

The first line contains the width of the array $n$, a positive integer of at most 1,024. The second line contains an integer $k$, the number of 1s in the array. Then $k$ lines follow, one for each entry with value 1. Each line contains two integers $x$ and $y$, which means $A[x, y] = 1$.

Since $n$ may be as large as 1,024, your program has to run fast enough to handle arrays of that size.

Print one integer, the width of the largest hole. If the array has no hole, print 0.

The figure below shows the array of the first example. The entry $A[i, j]$ sits at row $i$ and column $j$, and the arrow points to the location of $A[3, 7]$.

In this array there is a hole of width 3 at $(0, 0)$, and no hole of width 4 at $(0, 0)$. The largest hole has width 5 and sits at $(1, 2)$. The highlighted square in the figure is that hole.

Several fast methods find the largest hole. Below are hints to two different methods.

Hint 1: Consider these two values.

• $d_1$: the width of the largest hole that fits at $(1, 1)$
• $d_2$: the width of the largest hole that fits at $(2, 2)$

What is the relationship between $d_1$ and $d_2$? If you know $d_2$, is there a fast way to compute $d_1$?

Hint 2: Consider these two values.

• $s_1$: the number of 1s inside the square at $(0, 0)$ with width 7
• $s_2$: the number of 1s inside the square at $(0, 1)$ with width 7

What is the relationship between $s_1$ and $s_2$? If you know $s_1$, is there a fast way to compute $s_2$?