考古发掘区 - ROJ

考古学家在探索一座 $n \times n$ 的古代遗迹遗址时，试图在其中布置一个正方形的考古发掘区。然而，遗址中有 $T$ 块区域已经被标记为危险区，无法进行发掘。

你的任务是帮他们确定：在不包含任何危险区域的前提下，考古发掘区（正方形）的最大可能边长是多少。

第一行一个整数 $n$ ，表示遗址的边长。

第二行一个整数 $T$ ，表示有多少个危险区域。

接下来 $T$ 行，每行两个整数 $x, y$ ，表示第 $x$ 行第 $y$ 列是一个危险区域。

一行一个整数，表示可以布置的最大正方形发掘区的边长。

对于 20% 的数据， $1\leq n\leq 50,T=1$ 。

对于 40% 的数据， $1\leq n\leq 50,1\leq T\leq 10$ 。

对于 70% 的数据， $1\leq n\leq 5\times 10^5,1\leq T\leq 10$ 。

对于 100% 的数据， $1\leq n\leq 5\times 10^5,1\leq T\leq 100$ 。

5
1
2 4

见下发文件，满足 $1\leq n\leq 50,1\leq T\leq 10$ 。

见下发文件。

下发数据