#include<bits/stdc++.h>

using namespace std;

#define ll long long 
#define endl "\n"

ll n,m;
void solve(){
    vector<pair<int,int>> vp(m);
    for(auto&p:vp) cin>>p.first>>p.second;
    vector<vector<int>> in(n),out(n);
    multiset<int> se;
    int ans = n+1;
    for(int i =0;i<m;i++){
        int l = vp[i].first,r = vp[i].second;
        l--;r--;
        if(l>r) swap(l,r);
        if(l==r) continue;

        int len = r-l;
        if(l==0) se.insert(n-len);
        in[l].push_back(n-len);
        out[r].push_back(n-len);

        if(l) se.insert(len);
        in[r].push_back(len);
        if(l) out[l].push_back(len);
    }
    if(se.size()) ans = *prev(se.end());
    for(int i =1;i<n;i++){
        for(int x:in[i]) se.insert(x);
        for(int x:out[i]) se.erase(se.find(x));
        if(se.size()) ans = *prev(se.end());
    }
    if(ans==n+1) cout<<0<<endl;
    else cout<<ans<<endl;
}

signed main(){
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    while(cin>>n>>m){
        solve();
    }
}
/*
3 2
1 2
2 3
3 2
1 1
2 2
3 3
1 2
2 3
3 1
*/