#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,m,mp[1010][1010]={0},cx[1010]={0},da=0;
int main()
{
	freopen("bigbrn.in","r",stdin);
	freopen("bigbrn.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		mp[t1][t2]=-1;
	}
	/*
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			cout<<mp[i][j]<<' ';
		}
		cout<<endl;
		cout<<endl;
	}
	*/
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			if(mp[i][j]==0)
			{
				++cx[j];
			}
			else
			{
				cx[j]=0;
			}
		}
		/*
		for(int j=1;j<=n;++j)
		{
			cout<<cx[j]<<' ';
		}
		cout<<endl;
		*/
		for(int j=1;j<=n;++j)
		{
			int t1=1;
			for(int k=j+1;k<=n;++k)
			{
				if(cx[k]<cx[j])
				{
					break;
				}
				++t1;
			}
			for(int k=j-1;k>=1;--k)
			{
				if(cx[k]<cx[j])
				{
					break;
				}
				++t1;
			}
			da=max(da,min(t1,cx[j]));
		}
	}
	printf("%d\n",da);
	return 0;
}