#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;

}