#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MxM=200002;
int n,m,l,r,mid;
int a[MxM],b[MxM],cnt[MxM];
template<class T>void read(T &x)
{
	x=0;int f=0;char ch=getchar();
	while(ch<'0' || ch>'9')f|=(ch=='-'),ch=getchar();
	while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	x=f? -x:x;return ;
}
inline bool check()
{
	//printf(" check %d\n",mid);
	for(int i=1;i<=n;++i)cnt[i]=0;
	int t=0;
	for(int i=1;i<=m;++i)
	{
		if(a[i]-b[i]>mid && b[i]-a[i]+n>mid)return 0;
		if(a[i]-b[i]<=mid && b[i]-a[i]+n<=mid)continue;
		++t;
		if(a[i]-b[i]>mid)
		{
			//printf(" %d ~ %d\n",b[i],a[i]-1);
			++cnt[b[i]];
			--cnt[a[i]];
		}
		if(b[i]-a[i]+n>mid)
		{
			//printf(" 1 ~ %d and %d ~ n\n",b[i]-1,a[i]);
			++cnt[1];
			--cnt[b[i]];
			++cnt[a[i]];
		}
	}
	for(int i=1;i<=n;++i)cnt[i]+=cnt[i-1];
	//for(int i=1;i<=n;++i)printf("%d%c",cnt[i],i==n? '\n':' ');
	for(int i=1;i<=n;++i)if(cnt[i]==t)return 1;
	return 0;
}
int main()
{
	for(;~scanf("%d%d",&n,&m);)
	{
		for(int i=1;i<=m;++i)
		{
			read(a[i]),read(b[i]);
			if(a[i]<b[i])swap(a[i],b[i]);
		}
		for(l=1,r=n;l<=r;)
		{
			mid=((l+r)>>1);
			if(check())r=mid-1;
			else l=mid+1;
		}
		printf("%d\n",l);
	}
	return 0;
}