#MX99. Discover

Discover

题目描述

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

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

输入格式

第一行一个整数 nn,表示遗址的边长。

第二行一个整数 TT,表示有多少个危险区域。

接下来 TT 行,每行两个整数 x,yx, y,表示第 xx 行第 yy 列是一个危险区域。

输出格式

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

数据规模与约定

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

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

对于 70% 的数据,1≤n≤5×105,1≤T≤101\leq n\leq 5\times 10^5,1\leq T\leq 10 。

对于 100% 的数据,1≤n≤5×105,1≤T≤1001\leq n\leq 5\times 10^5,1\leq T\leq 100 。

样例

样例 输入样例1 输入

5
1
2 4

样例 输出样例1 输出

3

样例 输入样例2 输入

15
8
4 7
4 1
14 11
10 6
13 4
4 10
10 3
9 14

样例 输出样例2 输出

7

输入/输出样例3

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

输入/输出样例4

见下发文件。