/*一开始没认真读题，做成长方形，其实是正方形。读了题之后感觉和以前做的一道P1387 最大正方形很像，因为觉得该题是长方形，所以没在意，但是。。。。题目中说是正方形，那就和 P1387 最大正方形 一样了。。

转移方程：dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])

为什么是min不是max，画图可以知道，如果取max，那么可能会有树出现。

*/ 

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int n,t,x,y,ans;

int map[][],dp[][];

inline int read(int &num)

{

    num=;char c=getchar();

    for(;!isdigit(c);c=getchar());

    for(;isdigit(c);c=getchar()){num=num*+c-'';}

}

int main()

{

    read(n),read(t);

    for(int i=;i<=t;i++)

    {

        read(x),read(y);

        map[x][y]=;    //标记当前位置为数

    }

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=n;j++)

        {

            if(!map[i][j])        //当前位置不是树

            {

                dp[i][j]=min(dp[i-][j-],min(dp[i-][j],dp[i][j-]))+;

                ans=max(ans,dp[i][j]);        //取最大的边长

            }

        }

    }

    printf("%d",ans);

    return ;

}