#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define db double
#define fi first
#define se second
#define pii pair<int,int>
#define vi vector<int>

using namespace std;

const int maxn=5e5; 
int n,m;
vector<int> G[maxn+5];  
int MX(multiset<int> &S) {
	multiset<int>::iterator it=S.end(); 
	it--; 
	return *it;
} 
int main() {
	while (cin>>n>>m){ 
		multiset<int> S;
		S.clear();
		for (int i=1;i<=2*n;i++) G[i].clear(); 
		for (int i=1;i<=m;i++) {
			int u,v; 
			scanf("%d %d",&u,&v);
			if (u>v) swap(u,v); 
			G[u].push_back(v); 
			S.insert(v-u); 
		}
		int ans=1e9; 
		for (int i=1;i<=n;i++) {
			ans=min(ans,MX(S)); 
			for (auto v:G[i]) {
				S.erase(S.find(v-i));
				S.insert(i+n-v); 
				G[v].push_back(i+n);  
			}
		}
		cout<<ans<<'\n'; 
	}
	return 0;
}