Ron 想在他 N×N 的正方形院子里建造一个正方形游泳池，但他的院子里有 T 棵树。

你的任务是确定他能建造的最大正方形游泳池的边长。

输入的第一行是一个整数 N，其中 N ≥ 2。第二行是一个正整数 T，其中 T < N²。接下来的输入包含 T 行，每行表示一棵树的位置。

位置由两个正整数 R 和 C 给出，中间用空格分隔。每棵树位于第 R 行第 C 列，其中行从上到下编号为 1 到 N，列从左到右编号为 1 到 N。没有两棵树位于同一位置。

下表显示了 15 分的分布情况。

数据范围与提示

对于 20% 的数据：1 ≤ n ≤ 50, T = 1

对于 35% 的数据：1 ≤ n ≤ 50, 1 ≤ T ≤ 10

对于 25% 的数据：1 ≤ n ≤ 5×10⁵, 1 ≤ T ≤ 10

对于 100% 的数据：1 ≤ n ≤ 5×10⁵, 1 ≤ T ≤ 100

输出一行，包含一个整数 M，表示最大的正整数，使得 Ron 的院子里存在一个 M×M 的正方形区域不包含任何一棵树。