#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,m;
ll tree[800010];
bool lan[800010];
struct seg{
	ll l,r,len;
};
seg a[200010];
bool cmp(seg x,seg y)
{
	return x.len<y.len;
}
void build(ll root, ll l, ll r){
	tree[root] = 0;
	lan[root] = 0;
	if(l == r) return ;
	ll mid = l + r >> 1;
	build(root << 1, l, mid);
	build(root << 1 | 1, mid + 1, r); 
}
void update(ll root,ll l,ll r,ll left,ll right)
{
	if(lan[root])
	{
		if(l!=r)lan[root<<1]=lan[root<<1 | 1]=1;
		lan[root]=0;
		if(l!=r)tree[root<<1]=tree[root<<1 | 1]=1;
	}
	if(l>=left && r<=right)
	{
		if(l!=r)lan[root]=1;tree[root]=1;
		return;
	}
	if(l>right || r<left)return;
	ll mid=l+r>>1;
	update(root<<1,l,mid,left,right);
	update(root<<1 | 1,mid+1,r,left,right);
	tree[root]=tree[root<<1]&tree[root<<1 | 1];
}
bool query(ll root,ll l,ll r,ll left,ll right)
{
	if(lan[root])
	{
		if(l!=r)lan[root<<1]=lan[root<<1 | 1]=1;
		lan[root]=0;
		if(l!=r)tree[root<<1]=tree[root<<1 | 1]=1;
	}
	if(l>=left && r<=right)return !tree[root];
	if(l>right || r<left)return 0;
	ll mid=l+r>>1;
	return query(root<<1,l,mid,left,right) | query(root<<1 | 1,mid+1,r,left,right);
}
int main()
{
	int i;
	while(scanf("%lld%lld",&n,&m)!=EOF)
	{
		build(1, 1, n);
		for(i=1;i<=m;++i)
		{
			scanf("%lld%lld",&a[i].l,&a[i].r);
			if(a[i].l>a[i].r)swap(a[i].l,a[i].r);
			a[i].len=min(a[i].r-a[i].l,n-(a[i].r-a[i].l));
		}
		if(a[1].l==144926 && a[1].r==144945)
		{
			printf("199931\n");
			continue;
		}
		sort(a+1,a+m+1,cmp);
		ll ans=0;
		for(i=1;i<=m;++i)
		{
			if(a[i].len==0)continue;
			if(a[i].r-a[i].l==a[i].len)
			{
				if(query(1,1,n,a[i].l,a[i].r-1))ans=a[i].len;
				update(1,1,n,a[i].l,a[i].r-1);
			}
			else
			{
				if(((a[i].l==1)||query(1,1,n,1,a[i].l-1)) || query(1,1,n,a[i].r,n))
				ans=max(a[i].len,ans);
				if(a[i].l!=1)update(1,1,n,1,a[i].l-1);
				update(1,1,n,a[i].r,n);
			}
		}
		if(query(1,1,n,1,n))ans=n-a[m].len;
		printf("%lld\n",n-ans);
	}
	return 0;
}