POJ 1944

#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF=0x3f3f3f3f;
const int M=1010;
int n,p,ans,now;
int g[10*M][2],con[M<<1];

int main(){
	scanf("%d%d",&n,&p);
	for(int i=1;i<=p;i++)
		scanf("%d%d",&g[i][0],&g[i][1]);
	int a,b,now,i,j;
	for(i=1,ans=INF;i<=n;i++){
		memset(con,0,sizeof(con));
		now=0;
		for(j=1;j<=p;j++){
			a=g[j][0];
			if(a<i) a+=n;
			b=g[j][1];
			if(b<i) b+=n;
			if(a>b) swap(a,b);
			con[a]=max(con[a],b);
		}
		for(j=a=i;j<i+n;j++)
			if(con[j]>a){
				now+=con[j]-max(a,j);
				a=con[j];
			}
		ans=min(now,ans);
	}
	printf("%d\n",ans);
	return 0;
}