/*
    一开始题目看的不是很懂，看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; 
}