The Giant Barn

Problem Description

Farmer John wants to build a large square barn on his square-shaped farm. He hates cutting down trees, so he wants to find a spot on open, tree-free ground to build it. Suppose his farm is divided into an $n \times n$ grid. The input includes a list of squares that contain a tree. Your task is to compute and output the side length of the largest square barn he can build without cutting down any tree. The sides of the barn must be parallel to the horizontal and vertical axes.

Consider the grid below representing Farmer John's farm, where . denotes a square without a tree and # denotes a square with a tree. The largest barn that fits is $5 \times 5$.

........
.#...#..
........
........
........
..#.....
........
........

Input Format

The first line contains two positive integers: $n$ ($1 \leq n \leq 1000$), the size of the farm, and $T$ ($1 \leq T \leq n \times n$), the number of tree squares.

The following $T$ lines each contain two integers, the row and column coordinates of a tree square. Any two tree squares are guaranteed to be distinct.

Output Format

Output one positive integer: the maximum side length of a barn that can be built.

Sample Input

8 3
2 2
2 6
6 3

Sample Output

5

Constraints

$1 \leq n \leq 1000$.

Hint

• The barn must be axis-aligned (sides parallel to the grid).
• Brute force over every possible top-left corner and side length, and check whether the square is tree-free.