#include <bits/stdc++.h>
using namespace std;
typedef double db;
//#define int long long
#define fi first
#define se second
#define mk make_pair
#define pb emplace_back
#define poly vector<int>
#define Bt(a) bitset<a>
#define bc __builtin_popcount
#define pc putchar
#define ci const int&
const int mod = 998244353;
const db eps = 1e-10;
inline int Max(ci x, ci y) {return x > y ? x : y;}
inline int Min(ci x, ci y) {return x < y ? x : y;}
inline db Max(db x, db y) {return x - y > eps ? x : y;}
inline db Min(db x, db y) {return x - y < eps ? x : y;}
inline int Add(ci x, ci y, ci M = mod) {return (x + y) % M;}
inline int Mul(ci x, ci y, ci M = mod) {return 1ll * x * y % M;}
inline int Dec(ci x, ci y, ci M = mod) {return (x - y + M) % M;}
typedef pair<int, int> pii;
inline int Abs(int x) {return x < 0 ? -x : x;}
//char buf[1<<21],*p1=buf,*p2=buf;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char Obuf[105000],*O=Obuf;//Siz shoule be the size of Out File
int pst[30],ptop;
inline void Fprint(){fwrite(Obuf,1,O-Obuf,stdout);}
inline void Fwrite(int x){
  if(x==0){*O++='0';if(O-Obuf>100000)Fprint(),O=Obuf;return;}
  if(x<0)*O++='-',x=-x;ptop=0;
  while(x)pst[++ptop]=x%10,x/=10;
  while(ptop)*O++=pst[ptop--]+'0';
  if(O-Obuf>100000)Fprint(),O=Obuf;
}
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') w = -1;ch = getchar();}
    while (isdigit(ch)) {s = s * 10 + ch - '0';ch = getchar();}
    return s * w;
}
inline void write(int x) {
    if (x < 0)putchar('-'), x = -x;
    if (x > 9)write(x / 10);
	pc(x % 10 + '0');
}
inline int qpow(int x, int y) {
    int res = 1;
    while (y) {if (y & 1)res = Mul(res, x);x = Mul(x, x);y >>= 1;}
    return res;
}
inline void cadd(int &x, int y) {x += y;}
inline void cmul(int &x, int y) {x *= y;}
inline void cmax(int &x, int y) {x = Max(x, y);}
inline void cmin(int &x, int y) {x = Min(x, y);}
const int N = 5e5 + 10;
const int inf = 1 << 30;
namespace Refined_heart{
	int n,m;
	namespace SGT{
		int rt=0,node=0;
		int tag[N],minn[N];
		int ls[N],rs[N];
		inline void pushup(int x){
			minn[x]=Min(minn[ls[x]],minn[rs[x]]);
		}
		void reset(){
			rt=0;node=0;
		}
		void build(int &x,int L,int R){
			if(!x)x=++node;
			tag[x]=inf;minn[x]=inf;
			if(L==R)return;
			int mid=(L+R)>>1;
			build(ls[x],L,mid);
			build(rs[x],mid+1,R);
		}
		void pushm(int x,int v){
			cmin(tag[x],v);
			cmin(minn[x],v);
		}
		inline void pushdown(int x){
			if(tag[x]!=inf){
				int &p=tag[x];
				pushm(ls[x],p);
				pushm(rs[x],p);
				p=inf;
			}
		}
		void change(int x,int L,int R,int l,int r,int v){
			if(r<l)return;
			if(L>=l&&R<=r){
				pushm(x,v);
				return;
			}
			int mid=(L+R)>>1;
			pushdown(x);
			if(l<=mid)change(ls[x],L,mid,l,r,v);
			if(mid<r)change(rs[x],mid+1,R,l,r,v);
			pushup(x);
		}
		int query(int x,int L,int R,int pos){
			if(L==R)return minn[x];
			int mid=(L+R)>>1;
			pushdown(x);
			if(pos<=mid)return query(ls[x],L,mid,pos);
			return query(rs[x],mid+1,R,pos);
		}
	}
	int a[N],b[N];
	using namespace SGT;
	void clear(){
		SGT::reset();
	}
	
	void work(){
		for(int i=1;i<=m;++i){
			if(a[i]==b[i]){
				cout<<"0\n";
				return;
			}
			if(a[i]>b[i])swap(a[i],b[i]);
			int v=b[i]-a[i];
			if(v<n-v){
//				puts("E");
//				cout<<a[i]<<" "<<b[i]-1<<"\n";
//				cout<<1<<" "<<a[i]-1<<"\n";
//				cout<<b[i]<<" "<<n<<"\n";
				change(rt,1,n,a[i],b[i]-1,b[i]-a[i]);
//				puts(">");
				change(rt,1,n,1,a[i]-1,n-v);
//				puts(">");
				change(rt,1,n,b[i],n,n-v);
//				puts("D");
			}
			else{
//				puts("EE");
				swap(a[i],b[i]);
				//[a[i],n],[1,b[i]-1]
				v=n-v;
				change(rt,1,n,1,b[i]-1,v);
				change(rt,1,n,a[i],n,v);
				change(rt,1,n,b[i],a[i],n-v);
//				puts("DD");
			}
		}
		int ans=inf;
		for(int i=1;i<=n;++i){
			int v=query(rt,1,n,i);
			cmin(ans,n-v);
		}
		cout<<ans<<"\n";
	}
	void solve(){
		while(~scanf("%d%d",&n,&m)){
			clear();
			build(rt,1,n);
//			puts(">");
			for(int i=1;i<=m;++i){
				a[i]=read();
				b[i]=read();
			}
			work();
			
		}
	}
}
signed main(){
	Refined_heart::solve();
	return 0;
}