#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
#define re register
#define N 202000
#define pii pair<int,int>
#define fi first
#define se second
#define ll long long
using namespace std;
const int mo=998244353;
inline int read(){
	int x=0,w=0;char ch=getchar();
	while (!isdigit(ch))w|=ch=='-',ch=getchar();
	while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return w?-x:x;
}
int n,m,q,a[N],b[N],gg[N],f[N];
bool ck(int x){
	set<int>s;
	for (int i=1;i<=n;++i)s.insert(i);
	for (int i=1;i<=m;++i){
		if (a[i]>b[i])swap(a[i],b[i]);
		int mx=max(n-(b[i]-a[i]),b[i]-a[i]),mn=min(n-(b[i]-a[i]),b[i]-a[i]);
		if (mn>x)return 0;
		if (mx<=x)continue;
		if (b[i]-a[i]==mn){
			auto x=s.lower_bound(a[i]);
			while (x!=s.end()&&*x<b[i]){
				auto y=x;++x;
				s.erase(y);
			}
		}else{
			while (s.size()&&*s.begin()<a[i])s.erase(s.begin());
			while (s.size()&&*--s.end()>=b[i])s.erase(--s.end());
		}
	}
	return s.size();
}
void solve(){
	while (scanf("%lld%lld",&n,&m)!=EOF){
		for (int i=1;i<=m;++i)a[i]=read(),b[i]=read();
		int l=0,r=n,res=0;
		while (l<=r){
			int mid=(l+r)>>1;
			if (ck(mid))r=mid-1,res=mid;
			else l=mid+1;
		}
		printf("%lld\n",res);
	}
}
signed main(){
	solve();
    return 0;
}