#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,l,r) for(int i=(l); i<=(r); i++)
#define per(i,r,l) for(int i=(r); i>=(l); i--)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
const int N=2e5+5;
int n,m;
P eg[N];
int d[N],X;
bool ck(int res){
    rep(i,0,n)d[i]=0;
    auto add=[&](int l,int r){
        // cout<<l<<" "<<r<<endl;
        ++d[l]; --d[r];
    };
    rep(i,1,m){
        auto [u,v]=eg[i];
        if(u==v)continue;
        int v1=(v-u)<=res,v2=(u+n-v)<=res;
        // cout<<v1<<" "<<v2<<endl;
        if(v1 && v2)continue;
        else if(!v1 && !v2)return false;
        if(v1){
            add(u,v);
        }
        else if(v2){
            add(u,n+1); add(1,v);
        }
    }
    rep(i,1,n){
        d[i]+=d[i-1]; assert(d[i]>=0);
        if(!d[i]){X=i;return true;}
    }
    return false;
}
void slv(){
    rep(i,1,m){
        int u,v; cin>>u>>v;
        if(u>v)swap(u,v);
        eg[i]={u,v};
    }
    int L=0,R=n;
    // cout<<ck(1)<<endl; return;
    while(L<=R){
        int mid=(L+R)>>1;
        if(ck(mid))R=mid-1;
        else L=mid+1;
    }
    cout<<L<<"\n";
}
signed main(){
    IOS
    while(cin>>n>>m){
        slv();
    }
}