#include<bits/stdc++.h>
using namespace std;
int n,m;
void work(){
    vector<int>a(n+1),b(n+1);
    for (int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        if (a[i]>b[i]) swap(a[i],b[i]);
    }
    auto pd=[&](int mid){
        vector<int>p(n+3);
        for (int i=1;i<=m;i++){
            int x1=b[i]-a[i],x2=n-x1;
            if (min(x1,x2)>mid) return false;
            if (max(x1,x2)<=mid) continue;
            if (x1<=mid) p[a[i]]++,p[b[i]]--;
            else{
                p[b[i]]++,p[n+1]--;
                p[1]++,p[a[i]]--;
            }
        }
        for (int i=1;i<=n;i++){
            p[i]=p[i-1]+p[i];
            if (p[i]==0) return true;
        }
        return false;
    };
    int l=0,r=n,mid;
    while (l<r){
        mid=(l+r)/2;
        if (pd(mid)) r=mid;
        else l=mid+1;
    }
    cout<<l<<'\n';
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    #ifdef LC
    freopen("t.in","r",stdin);
    freopen("t.out","w",stdout);
    #endif
    while (cin>>n>>m)
        work();
}