#include<queue>
#include<cmath>
#include<vector>
#include<time.h>
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define lp p<<1
#define rp (p<<1)+1
using namespace std;

template<typename T>void read(T &x){
    x=0;int w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x=x*w;
}

typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=4e5+5;

int n,m,a[N],b[N];

struct pp{
	int x,y;
}t[N];
int cmp(pp aa,pp bb){return aa.x<bb.x;}

int pd(int mid){
	int num=0;
	for(int i=1;i<=m;i++){
		if(a[i]==b[i])continue;
		int d1=b[i]-a[i],d2=n-b[i]+a[i];
		if(d1>mid&&d2>mid)return 0;
		if(d1<=mid&&d2>mid)
		t[++num].x=a[i],t[num].y=b[i];
		if(d2<=mid&&d1>mid){
			t[++num].x=1;t[num].y=a[i];
			t[++num].x=b[i];t[num].y=n+1;
		}
	}
	sort(t+1,t+1+num,cmp);
	if(t[1].x!=1)return 1;
	int lr=t[1].y;
	for(int i=1;i<=num;i++)
	if(t[i].x<=lr)lr=max(lr,t[i].y);
	else{
		if(lr!=n+1)return 1;
	}
	if(lr==n+1) return 0;
	else return 1;
}
void solve(){
	int ff=0;
	for(int i=1;i<=m;i++){
		read(a[i]);read(b[i]);
		if(a[i]!=b[i])ff=1;
		if(a[i]>b[i])swap(a[i],b[i]);
	}
	if(!ff){
		printf("0\n");
		return;
	}
	int l=1,r=n*2,ans=n;
	while(l<=r){
		int mid=(l+r)/2;
		if(pd(mid)) ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%d\n",ans);
}

int main(){
	while(scanf("%d%d",&n,&m)!=EOF)solve();
	return 0;
}