#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define int ll
#define ms(a,b) memset((a),(b),sizeof(a))
#define mc(a,b) memcpy((a),(b),sizeof(a))
#define PI acos(-1)
#define ssin(x) sin(x*PI/180.00)
#define ccos(x) cos(x*PI/180.00)
#define ttan(X) tan(x*PI/180.00)
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, n, a) for (int i = n - 1; i >= a; i--)
#define IOS ios::sync_with_stdio(false)
#define si(x) scanf("%d",&x)
#define sii(x, y) scanf("%d %d",&x, &y)
#define siii(x, y, z) scanf("%d %d %d",&x, &y, &z)
#define siiii(x, y, z, w) scanf("%d %d %d %d",&x, &y, &z, &w)
#define sl(x) scanf("%lld",&x)
#define sll(x, y) scanf("%lld %lld",&x, &y)
#define slll(x, y, z) scanf("%lld %lld %lld",&x, &y, &z)
#define sllll(x, y, z, w) scanf("%lld %lld %lld %lld",&x, &y, &z, &w)
#define pr(x) printf("%d",x)
#define pl(x) printf("%lld",x)
#define sd(x) scanf("%lf",&x)
#define sdd(x, y) scanf("%lf %lf",&x, &y)
#define sddd(x, y, z) scanf("%lf %lf %lf",&x, &y, &z)
#define sdddd(x, y, z, w) scanf("%lf %lf %lf %lf",&x, &y, &z, &w)
#define fi first
#define se second
#define pb push_back
#define mk make_mair

using namespace std;

typedef unsigned long long ull;

typedef pair<int, int> PII;

const int mod = 998244353;

const int P = 131;

const int N = 1e5 + 10, M = 3e6 + 10;

const int inf = 0x3f3f3f3f;

const ll lnf = 9e18;

const double eps = 1e-6;

int n, m;
struct F {
	int a, b, len;
} f[N];
map<int, int> ma;

bool cmp (F x, F y) {
	return x.len < y.len;
}

void solve() {
	while (~scanf ("%lld %lld", &n, &m) ) {
		ma.clear();
		int res = 0, cnt = 0;

		for (int i = 0; i < m; i ++) {
			int x, y;
			sll (x, y);

			if (y - x < n - (y - x) ) {
				f[i] = {x, y, y - x};
			}
			else {
				f[i] = {x, y, n - (y - x) };
			}

			res = max (res, f[i].len);
		}

		sort (f, f + m, cmp);

		for (int i = 0; i < m; i ++) {
			if (f[i].a > f[i].b) {
				for (int j = f[i].a; j < f[i].b + n; j ++) {
					if (!ma.count (j % n) ) {
						ma[j % n] = f[i].len;
						cnt++;
					}
				}
			}
			else {
				for (int j = f[i].a; j < f[i].b; j ++) {
					if (!ma.count (j % n) ) {
						ma[j % n] = f[i].len;
						cnt++;
					}
				}
			}

			if (cnt == n)
				break;
		}

//		cout<<cnt<<endl;

		if (cnt != n) {
			for (int i = 1; i <= n; i ++) {
				if (!ma.count (i) ) {
					printf ("%lld\n", res);
					break;
				}
			}
		}
		else {
			int cc = 0;

			for (int i = 1; i <= n; i ++) {
				cc = max (cc, ma[i]);
			}

			printf ("%lld\n", n - cc);
		}
	}
}

signed main() {
	//	IOS;
	//	cin.tie (0);
	//	cout.tie (0);
	int T (1);
	//	sl (T);

	while ( T-- ) {
		solve();
	}

	return 0;
}

/*
3 2
1 2
2 3
3 2
1 1
2 2
3 3
1 2
2 3
3 1
*/