#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T1,class T2> bool cmin(T1 &x,const T2 &y) { if (y<x) { x=y; return 1; }return 0; }
template<class T1,class T2> bool cmax(T1 &x,const T2 &y) { if (x<y) { x=y; return 1; }return 0; }
#define all(x) (x).begin(),(x).end()
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	int n,m,i,j;
	while (cin>>n>>m)
	{
		multiset<int> s;
		vector<vector<pair<int,int>>> cg(n);
		while (m--)
		{
			int u,v;
			cin>>u>>v;
			--u; --v;
			if (u>v) swap(u,v);
			s.insert(v-u);
			cg[u].push_back({v-u,n-(v-u)});
			cg[v].push_back({n-(v-u),v-u});
		}
		int ans=*s.rbegin();
		for (i=0; i<n-1; i++)
		{
			for (auto [x,y]:cg[i])
			{
				s.extract(x);
				s.insert(y);
			}
			cmin(ans,*s.rbegin());
		}
		cout<<ans<<'\n';
	}
}