#include <bits/stdc++.h>  
using namespace std;  

#define int long long  

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

	int n, m;
	cin >> n >> m;

	while (cin >> n >> m) {
		vector<pair<int, int>> t(m);
		for (auto &[x, y] : t) {
			cin >> x >> y;
			if (x > y) {
				swap(x, y);
			}
		}

		auto check = [&](int d) {
			vector<int> cnt(n + 1);
			auto add = [&](int l, int r) {
				cnt[l]++;
				if (r < n) {
					cnt[r + 1]--;
				}
			};
			for (auto [x, y] : t) {
				if (x == y) {
					add(1, n);
					continue;
				}
				int d1 = y - x;
				int d2 = n - d1;

				if (d1 <= d && d2 <= d) {
					add(1, n);
				} else if (d1 > d && d2 <= d) {
					add(x, y - 1);
				} else if (d1 <= d && d2 > d) {
					if (x > 1) {
						add(1, x - 1);
					}
					add(y, n);
				} else {
					return false;
				}
			}
			int s = 0;
			for (int i = 1; i <= n; i++) {
				s += cnt[i];
				if (s == m) {
					return true;
				}
			}
			return false;
		};

		int l = -1, r = n;
		while (l + 1 != r) {
			int mid = (l + r) / 2;
			if (check(mid)) {
				r = mid;
			} else {
				l = mid;
			}
		}

		cout << r << "\n";
	}

    return 0;
}