#include<bits/stdc++.h>
using namespace std;
#define maxn 400010
#define PII pair<int,int>
#define PIII pair<int ,PII>
int tree[maxn << 2];
void pushdown(int root){
    if(tree[root]>0){
        tree[root * 2] = tree[root * 2 + 1] = tree[root];
        tree[root] = -1;
    }
}
void build(int l,int r,int root){
    if(l==r){
        tree[root] = -1;
        return;
    }
    int mid = l + (r - l) / 2;
    build(l, mid, root * 2);
    build(mid + 1, r, root * 2 + 1);
}
void update(int fl,int fr,int l,int r,int k,int root){
    if(fl<=l&&r<=fr){
        tree[root] = k;
        //cout << "?? " <<root<<" "<< k << endl;
        return;
    }
    pushdown(root);
    int mid = l + (r - l) / 2;
    if(fl<=mid)
        update(fl, fr, l, mid, k, root * 2);
    if(fr>mid)
        update(fl, fr, mid + 1, r, k, root * 2 + 1);
}
int res[maxn];
int top = 0;
void query(int l,int r,int root){
    if(l==r){
        res[++top] = tree[root];
        //cout << top << " " << root << " " << tree[root] << endl;
        return;
    }
    int mid = l + (r - l) / 2;
    pushdown(root);
    query(l, mid, root * 2);
    query(mid + 1, r, root * 2 + 1);
}
int main(void){
    int n, m;
    while(scanf("%d%d",&n,&m)!=EOF){
        top = 0;
        //build(1, n, 1);
        memset(tree, -1, sizeof(tree));
        vector<PIII>v;
        int mn = 0;
        for (int i = 1;i<=m;i++){
            int a, b;
            scanf("%d%d", &a, &b);
            int len;
            if(a>b){
                swap(a, b);
            }
            mn = max(mn,min(b - a, n - (b - a)));
            len = max(b - a, n - (b - a));
            if(a==b)continue;
            v.push_back({len, {a, b}});
        }
        sort(v.begin(), v.end());
        for(auto x:v){
            //cout << x.first << endl;
            //x.first==big
            int a, b;
            a = x.second.first;
            b = x.second.second;
            if(x.first!=b-a){
                update(a, b-1, 1, n, x.first, 1);
                //cout << "!" << a << " " << b << " " << x.first << endl;
            }
            else {
                //cout << "?" << a << " " << b << " " << x.first << endl;
                if(a>1)
                    update(1, a - 1, 1, n, x.first, 1);
                update(b, n, 1, n, x.first, 1);
            }
        }
        query(1, n, 1);
        int mnn = 1e9;
        for (int i = 1;i<=n;i++){
            //cout << res[i] << endl;
            mnn = min(mnn, res[i]);
        }
        if(mnn==-1){
            cout << mn << endl;
        }
        else
            cout << mnn << endl;
    }
    return 0;
}