Largest Square Swimming Pool

Ron wants to build a square swimming pool in his \(n \times n\) yard. However, his yard has \(T\) trees planted in it. The trees cannot be removed. Your task is to determine the maximum side length of a square swimming pool that can be built without covering any tree.

The input starts with two integers: n (the size of the yard) and T (the number of trees). Then T lines follow, each containing two integers representing the row and column coordinates of a tree (1-indexed).

The answer is a single integer representing the maximum side length of the square area free of trees.

Note: Use LaTeX format for any formulas (as shown above).

inputFormat

The first line contains two integers n and T separated by a space, where n (\(1 \leq n \leq 10^3\)) represents the dimensions of the yard and T (\(0 \leq T \leq n^2\)) is the number of trees.

Each of the next T lines contains two integers, r and c (\(1 \leq r, c \leq n\)), which denote the row and column positions of a tree. It is guaranteed that all tree positions are distinct.

outputFormat

Output a single integer representing the side length of the largest square swimming pool that can be built without covering any trees.

sample

5 3
2 2
3 5
5 3

2