#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MxM=200002;
int n,m,l,r,mid,l1,r1,l2,r2;
bool ok;
int a[MxM],b[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);
	l1=l2=1,r1=r2=n;
	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;
		if(a[i]-b[i]>mid)
		{
			//printf(" %d ~ %d\n",b[i],a[i]-1);
			l1=max(l1,b[i]);
			l2=max(l2,b[i]);
			r1=min(r1,a[i]-1);
			r2=min(r2,a[i]-1);
		}
		if(b[i]-a[i]+n>mid)
		{
			//printf(" 1 ~ %d and %d ~ n\n",b[i]-1,a[i]);
			r1=min(r1,b[i]-1);
			l2=max(l2,a[i]);
		}
	}
	return l1<=r1 || l2<=r2;
}
int main()
{
	for(;~scanf("%d%d",&n,&m);)
	{
		ok=0;
		for(int i=1;i<=m;++i)
		{
			read(a[i]),read(b[i]),ok|=(a[i]==b[i]);
			if(a[i]<b[i])swap(a[i],b[i]);
		}
		if(ok)
		{
			puts("0");
			continue;
		}
		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;
}