#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

using namespace std;

const int INF = ;

int a[],b[],dis[];

vector <int> vc;

int main(void)

{

    int n,m,i,j,p,k;

    while(~scanf("%d%d",&n,&k)){

        vc.clear();

        for(i=;i<k;i++){

            scanf("%d%d",&a[i],&b[i]);

            if(a[i]>b[i]) swap(a[i],b[i]);

            vc.push_back(a[i]);

            vc.push_back(b[i]);

        }

        vc.push_back();vc.push_back(n);

        sort(vc.begin(),vc.end());

        vc.erase(unique(vc.begin(),vc.end()),vc.end());

        memset(dis,INF,sizeof(dis));

        dis[]=;

        int len=vc.size();

        for(i=;i<len;i++)

            for(j=i+;j<len;j++){

                for(p=;p<len;p++)

                if(vc[i]==a[p]&&vc[j]==b[p]){

                    dis[j]=min(dis[i]+,dis[j]);

                }

                dis[j]=min(dis[j],dis[i]+__builtin_popcount(vc[j]-vc[i]));

            }

        printf("%d\n",dis[len-]);

    }

    return ;

}