#include<bits/stdc++.h>
int n,m;
#define maxn 200005
void solve() {
	std::vector<int> pop[maxn],push[maxn];
	for(int i = 1 ; i <= m; i++) {
		int x,y;
		std::cin >> x >> y;
		if (y < x) std::swap(x,y);
		if (x == y) continue;
		push[1].push_back(y-x);
		pop[x].push_back(y-x);
		push[x].push_back(n-(y-x));
		pop[y].push_back(n-(y-x));
		push[y].push_back(y-x);
	}
	std::multiset<int> st;
	int ans = 1e9;
	for(int i = 1; i <= n; i++) {
		for(auto j : push[i]) {
			st.insert(j);
		}
		for(auto j : pop[i]) {
			st.erase(st.find(j));
		}
		if (st.empty()) {
			std::cout << 0 << std::endl;
			return ;
		}
		// for(auto v : st) {
		// 	printf("%d ",v);
		// }putchar('\n');
		ans = std::min(ans, *st.rbegin());
	}
	std::cout << ans << std::endl;
}
int main() {
	std::ios::sync_with_stdio(0);
	while(std::cin >> n >> m) {
		solve();
	}
}