POJ 1944

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;
const int N=1005;
const int P=10005;
int d[N];
struct ei{
	int u,v;
}edge[P];

int main(){
	int n,p,u,v;
	while(scanf("%d%d",&n,&p)!=EOF){
		for(int i=0;i<p;i++){
			scanf("%d%d",&u,&v);
			edge[i].u=min(u,v);
			edge[i].v=max(u,v);
		}
		int mind=(1<<30);
		for(int i=1;i<=n;i++){
			memset(d,-1,sizeof(d));
			int ans=0,pos=-1;
			for(int e=0;e<p;e++){
				if(edge[e].u<=i&&edge[e].v>i){
					d[1]=max(d[1],edge[e].u);
					d[edge[e].v]=max(d[edge[e].v],n);
					ans=1;
				}
				else {
					d[edge[e].u]=max(d[edge[e].u],edge[e].v);
				}
			}
			for(int i=1;i<=n;i++){
				if(pos==-1&&d[i]!=-1){
					pos=i;
				}
				else{
					if(d[i]!=-1){
						if(i<=d[pos]&&d[i]>d[pos])
						d[pos]=d[i];
						else if(i>d[pos]){
							ans+=d[pos]-pos;
							pos=i;
						}
					}
				}
			}
			ans+=d[pos]-pos;
			mind=min(ans,mind);
		}
		printf("%d\n",mind);
	}
	return 0;
}