#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100000+10;
struct node{
    int x,y;
}a[maxn<<1];
struct node2{
    int id,l;
}b[maxn<<2];
int nxt[maxn<<1][25];
bool cmp(node2 x,node2 y){
    if(x.l==y.l) return x.id<y.id;
    return x.l<y.l;
}
int chkmax(int x,int y){return x>y?x:y;}
int main(){
    int m,n;
    cin>>m>>n;
    for(int i=1;i<=n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        if(x>y) y+=m;
        a[i].x=x; a[i].y=y;
        a[i+n].x=x+m; a[i+n].y=y+m;
    }
    int cnt=0;
    for(int i=1;i<=(n<<1);++i){
        b[++cnt].id=i+(n<<1);
        b[cnt].l=a[i].x;
        b[++cnt].id=i;
        b[cnt].l=a[i].y;
    }
    sort(b+1,b+1+(n<<2),cmp);
    int lst=-1;
    for(int i=(n<<2);i>=1;--i){
        int id=b[i].id;
        if(id>(n<<1)){
            id-=(n<<1);
            if(lst<0 || a[lst].y>a[id].y)
                lst=id;
        }else{
            nxt[id][0]=lst;
        }
    }
    for(int k=0;k<=19;++k)
        for(int i=1;i<=(n<<1);++i){
            if(nxt[i][k]==-1) nxt[i][k+1]=-1;
            else nxt[i][k+1]=nxt[ nxt[i][k] ][k];
        }
    int ans=0;
    for(int i=1;i<=n;++i){
        int tmp=0,j=i;
        for(int k=19;k>=0;--k){
            int t=nxt[j][k];
            if(t>0 && a[t].y<=a[i].x+m){
                j=t;
                tmp|=(1<<k);
            }
        }
        ans=chkmax(ans,tmp+1);
    }
    cout<<ans<<endl;
    return 0;
}