P8404 [CCC 2022 J5] Square Pool

Ron wants to build a square swimming pool in his $n \times n$ square yard, but there are $T$ trees in his yard. Your task is to determine the side length of the largest square swimming pool he can build.

The first line contains an integer $n$, as described in the problem statement. The second line contains an integer $T$, as described in the problem statement. The next $T$ lines each contain two integers $x, y$, indicating that there is a tree at $(x, y)$.

Output one line containing the maximum side length of the swimming pool.

Explanation for Sample $1$:  Explanation for Sample $2$:  Constraints: For $20\%$ of the testdata: $1 \le n \le 50, T = 1$. For $35\%$ of the testdata: $1 \le n \le 50, 1 \le T \le 10$. For $25\%$ of the testdata: $1 \le n \le 5 \times 10^5, 1 \le T \le 10$. For $100\%$ of the testdata: $1 \le n \le 5 \times 10^5, 1 \le T \le 100$. Translated by ChatGPT 5