#include <iostream>
#include <cstdio>
#include <cstring>
#include <utility>
using namespace std;
//英语 看博友分析 抄博友程序 求线段中多区间内的元素数 巧妙
int l[10008];//抄博友
int r[10008];
int a[1008];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++)
{
scanf("%d%d",&l[i],&r[i]);
}
int jg=-1;
for(int i=0;i<n;i++)//看博友分析
{
memset(a,0,sizeof(a));
for(int j=0;j<m;j++)
{
int x=(l[j]+n-i)%n;
int y=(r[j]+n-i)%n;
if(x>y)
{
swap(x,y);
}
a[x]++;//巧妙
a[y]--;
}
int t=0;
int js=0;
for(int i=0;i<n;i++)
{
t=t+a[i];
if(t>0)//抄博友程序
{
js++;
}
}
if(jg==-1||jg>js)
{
jg=js;
}
}
printf("%d\n",jg);
return 0;
}
