#include<bits/stdc++.h>
#define int long long 
#define fer(i,a,b) for(int i = a ; i <= b ; i ++)
using namespace std ;
using i64 = long long;
const int N = 1e6 + 10 ;

int n , m ;
int a[N] , b[N] ;
int c[N] ;

void get(int a , int b)
{
    if(a < b)
    {
        c[a] ++ , c[b] -- ;
    }
    else
    {
        //a -> n -> 1 -> b 
        c[a] ++ , c[n + 1] -- , c[1] ++ , c[b] -- ; 
    }
}

int get(int mid)
{
    fer(i,1,n) c[i] = 0 ;

    fer(i,1,n)
    {
        int l = a[i] , r = b[i] ;
        if(l > r) swap(l , r) ;
        
        int d1 = r - l ;
        int d2 = n - r + l ;

        //cout << l << " " << r << ' ' << d1 << " " << d2 << '\n' ;
        if(d1 <= mid && d2 <= mid)
        {
            get(1 , n + 1) ;
        }
        else if(d1 > mid && d2 > mid)
            return 0 ;
        else
        {
            if(d1 >= d2)
                get(l , r) ;
            else   
                get(r , l) ;
        }
    }

    fer(i,1,n)
    {
        c[i] += c[i - 1] ;
        //cout << c[i] << " \n"[i == n] ;
        if(c[i] >= n)
            return 1 ;
    }

    return 0 ;
}

void solve()
{
    fer(i,1,n)
        cin >> a[i] >> b[i] ;

    //get(1) ;
    // fer(i,0,n)
    //     cout << get(i) << '\n' ;

    int l = 0 , r = n ;
    while(l < r)
    {
        int mid = l + r >> 1 ;
        if(get(mid)) r = mid ;
        else l = mid + 1 ;
    }

    cout << l << '\n' ;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    while(cin >> n >> m)
        solve() ;
    
}