//什么时候我才能有杜爷一半强啊/kk
#include<cstdio>
const int N=200086,INF=1e9+7;
int n,m,ans,mx[N<<2],tag[N<<2];
bool Swap(int &a,int &b){a^=b^=a^=b;return true;}
int Max(int a,int b){return a>b?a:b;}
int Min(int a,int b){return a<b?a:b;}
int read(){
	char ch=getchar();int nn=0,ssss=1;
	while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
	return nn*ssss;
}
bool build(int k,int l,int r){
	mx[k]=tag[k]=0;if(l==r)return true;int mid=(l+r)>>1;
	return build(k<<1,l,mid)&&build(k<<1|1,mid+1,r);
}
bool pushdown(int k){
	if(!tag[k])return true;
	mx[k<<1]=Max(mx[k<<1],tag[k]);tag[k<<1]=Max(tag[k<<1],tag[k]);
	mx[k<<1|1]=Max(mx[k<<1|1],tag[k]);tag[k<<1|1]=Max(tag[k<<1|1],tag[k]);
	tag[k]=0;return true;
}
bool change(int k,int l,int r,int x,int y,int z){
	if(l>=x&&r<=y){mx[k]=Max(mx[k],z);tag[k]=Max(tag[k],z);return true;}
	int mid=(l+r)>>1;pushdown(k);
	if(x<=mid)change(k<<1,l,mid,x,y,z);
	if(mid<y)change(k<<1|1,mid+1,r,x,y,z);
	return true;
}
bool dfs(int k,int l,int r){
	if(l==r){ans=Min(ans,mx[k]);return true;}
	int mid=(l+r)>>1;pushdown(k);
	return dfs(k<<1,l,mid)&&dfs(k<<1|1,mid+1,r);
}
bool solve(){
	ans=INF;build(1,1,n);
	for(int i=1;i<=m;i++){
		int u=read();int v=read();if(u==v)continue;
		if(u>v)Swap(u,v);
		change(1,1,n,v,n,v-u);
		if(u>1)change(1,1,n,1,u-1,v-u);
		change(1,1,n,u,v-1,n-v+u);
	}
	dfs(1,1,n);printf("%d\n",ans);return true;
}
int main(){
	//freopen("F.in","r",stdin);
	while(~scanf("%d%d",&n,&m))solve();
}