// Duet of Dusk Embers--XrkArul
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ULL __int128_t
#define ull unsigned long long
#define vi vector<int>
#define vll vector<ll>
#define endl '\n'
#define ednl '\n'
#define pb push_back
#define fi first
#define se second
#define ls (p<<1)
#define rs (p<<1|1)
#define fix setprecision
#define all(v) v.begin(),v.end()
#define pii pair<int, int>
#define pll pair<ll, ll>
#define debug(x) cerr<<#x<<':'<<' '<<x<<'\n'
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define pq priority_queue<int, vector<int>>
#define PQ priority_queue<int, vector<int>, greater<int>>
const ll inf = 1e18;
const ll mod=1e9+7;
const ull hashbase = 5767169;
ll powmod(ll a,ll b){ll s=1;a%=mod;while(b){if(b&1)s=s*a%mod;b>>=1;a=a*a%mod;}return s%mod;}

#define int long long
void solve(){
    
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T=1;
    //cin>>T;
    int n,m;
    while(cin>>n>>m){
        multiset<int> s;
        vector<vector<pii>> qwq(n+10);
        int f=0;
        rep(i,1,m){
            int a,b;cin>>a>>b;
            if(a==b){
                continue;
            }
            if(a>b)swap(a,b);
            f=1;
            int len=b-a;
            qwq[a].pb({n-len,1});
            qwq[b].pb({n-len,-1});
            qwq[1].pb({len,1});
            qwq[a].pb({len,-1});
            qwq[b].pb({len,1});
            // qwq[n+1]
        }
        int ans=inf;
        if(!f){
            cout<<0<<endl;continue;
        }
        rep(i,1,n){
            sort(all(qwq[i]),[&](pii a,pii b){
                return a.se<b.se;
            });
            for(auto x:qwq[i]){
                if(x.se==-1){
                    if(!s.size())continue;
                    s.erase(s.find(x.fi));
                }else{
                    s.insert(x.fi);
                }
            }
            if(s.size())
            ans=min(ans,*(s.rbegin()));
        }
        cout<<ans<<endl;
    }
    return 0;
}
/*

*/