/*
    一開始題目看的不是很懂，看watashi的解題報告的

    題意：n個團員，坐成一排。團長列出m對關系，
    每分鐘報一個，如果關系中的兩個人相鄰，則其中一個人要離開
    團員想走的越多越好，團長想走的人越少越好，問團長該怎么安排
    這m對關系的順序

    顯然團長可以先貪心地把原本不相鄰的關系先報掉，這樣沒人會走
    接下來的就是一些連續的一段
    這個問題可以dp預處理，dp[n]表示n個人連成一段最少離開的人數

    團長會枚舉斷開的點然后縮小規模解決
    1 - 2 - 3  n-1 - n
    枚舉斷開第i段的話，現在團員當然會選擇讓離開的人最多
    即 max(dp[i-1]+dp[n-i]+1 , dp[i]+dp[n-i-1]+1)
    而團長就通過枚舉哪一段來取得最小值
    min{ max(dp[i-1]+dp[n-i]+1 , dp[i]+dp[n-i-1]+1) }
*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int INF = 1000000000;

int dp[512];

void init()
{
    dp[2] = 1;
    for(int n = 3 ; n <= 500 ; n++)
    {
        dp[n] = INF;
        for(int i = 1 ; i < n ; i++)
        {
            dp[n] = min( dp[n] , max(dp[i-1]+dp[n-i] , dp[i]+dp[n-i-1])+1 );
        }
    }
}

int main()
{
    //freopen("in","r",stdin);    
    init();
    int n , m;
    while(~scanf("%d%d",&n,&m) )
    {
        int a ,b;
        vector<int> vt;
        for(int i = 0 ; i < m ; i++)
        {
            scanf("%d%d",&a,&b);
            if(a>b)swap(a,b);
            if(b==a+1)
            {
                vt.push_back(a);
            }
        }
        sort(vt.begin() , vt.end());
        int ans = n;
        for(vector<int>::iterator it = vt.begin() ; it != vt.end();it++)
        {
            int cnt = 1;
            while( it+1 != vt.end() && (*it)+1 == *(it+1))cnt++,it++;
            cnt ++;
            ans -= dp[cnt];
        }
        printf("%d\n",ans);
    }    
    return 0; 
}