#include<algorithm>
#include<iostream>
#include<vector>
#include<cstdio>
using namespace std;
#define For(i,l,r) for(int i=l;i<=r;i++)
#define FOR(i,l,r) for(int i=l;i>=r;i--)
#define MAXN 200001
int N,M,u[MAXN],v[MAXN],p[MAXN],f[MAXN];
int get(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;}
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
int main()
{
	while(cin>>N>>M)
	{
		For(i,1,M)u[i]=get()-1,v[i]=get()-1,p[i]=i;For(i,0,N)f[i]=i;For(i,1,M)if(u[i]>v[i])swap(u[i],v[i]);
		sort(p+1,p+M+1,[&](const int&x,const int&y){return max(v[x]-u[x],N-v[x]+u[x])>max(v[y]-u[y],N-v[y]+u[y]);});int cnt=N,ans=-1;int flag=-1;
		For(i,1,M)
		{
			int x=u[p[i]],y=v[p[i]];if(y-x==N-y+x){flag=max(flag,N/2);continue;}if(x==y){flag=max(flag,0);continue;}
			if(y-x>N-y+x)
			{
				for(int i=getf(0);i<x;i=getf(i+1)){if(cnt==1){ans=y-x;break;}cnt--;f[getf(i)]=getf(i+1);}
				for(int i=getf(y);i<N;i=getf(i+1)){if(cnt==1){ans=y-x;break;}cnt--;f[getf(i)]=getf(i+1);}
			}
			else for(int i=getf(x);i<y;i=getf(i+1)){if(cnt==1){ans=N-y+x;break;}cnt--;f[getf(i)]=getf(i+1);}
			if(ans!=-1)break;flag=max(flag,min(y-x,N-y+x));
		}
		cout<<max(ans,flag)<<'\n';
	}
	return 0;
}