#pragma comment(linker, "/STACK:65777216")
#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <stack>
#include <map>
#include <queue>
#include <string>
#include <memory.h>
#include <iterator>
#define y1 trololoy1
#define y0 trololoy0
#define mem(A,X) memset(A,X,sizeof(A))
#define memo(A) memset(A,0,sizeof(A))
#define forn(I,B) for (int I=1;I<=(B);I++)
#define forg(H,V) for (int H=first[V];h;h=next[H])
#define rep(I,B) for (int I=0;I<(B);I++)
#define labs(X) (((X)>0)?(X):(-(X)))
#define ropen(X) freopen(X,"r",stdin)
#define wopen(X) freopen(X,"w",stdout)
#define rwopen(X) freopen(X".in","r",stdin);freopen(X".out","w",stdout)
#define pb push_back
#define mp make_pair
#define all(X) (X).begin(),(X).end()
#define sqr(X) ((X)*(X))

using namespace std;

typedef pair <int,int> pii;
typedef double ld;
typedef long long ll;
typedef pair <ll,ll> pll;
typedef vector<int> vi;
const int N=5555;
const int INF=111111111;
const double eps=1e-9;
const double pi=3.14159265358979;

struct seg{
    int bg,en,id;
} a[N],b[N],w[N];

struct qs{
    int bg,en,id,ans;
} t[N];

inline bool cmp1(seg a, seg b){
    return a.en-a.bg<b.en-b.bg;
}

inline bool cmp2(seg a,seg b){
    return a.en<b.en;
}

int k,n,f[N],g[N],ptr,p[N],q[N],l,r,mx[N];
bool used[N];

inline int bin_search(int x,int pos){
    int l=0,r=pos;
    if (t[0].en>x) return -1;
    while (l<r){
        int m=(l+r)/2;
        if (t[m].en<=x) l=m+1;
        else r=m;
    }
    if (t[l].en>x || l>pos) --l;
    return l;
}

inline void modify(int pos,int value){
    for(;pos<n;pos|=pos+1) if (mx[pos]<0 || g[mx[pos]]<g[value]) mx[pos]=value;
}

inline pii get_max(int pos){
    int best=-1;
    for(;pos>=0;pos=(pos&(pos+1))-1) if (mx[pos]>=0 && (best==-1 || g[mx[pos]]>g[best])) best=mx[pos];
    return mp(g[best],best);
}

inline void calc_g(){
    memo(g);
    if (ptr==0) return;
    g[0]=t[0].ans;
    p[0]=-1;
    mem(mx,128);
    modify(0,0);
    forn(i,ptr-1){
        g[i]=t[i].ans;
        p[i]=-1;
        int bs=bin_search(t[i].bg,i-1);
        if (bs!=-1){
            pii tt=get_max(bs);
            if (tt.first+t[i].ans>g[i]){
                g[i]=tt.first+t[i].ans;
                p[i]=tt.second;
            }
        }
        modify(i,i);
    }
}

void rec_ans(){
    w[n]=(seg){1,k,n};
    q[++r]=n;
    while (l!=r){
        int v=q[++l];
        ptr=0;
        rep(j,n) if (b[j].bg>=w[v].bg && b[j].en<=w[v].en && b[j].id!=w[v].id){
            t[ptr].bg=b[j].bg;
            t[ptr].en=b[j].en;
            t[ptr].id=b[j].id;
            t[ptr].ans=f[b[j].id];
            ++ptr;
        }
        if (ptr==0) continue;
        calc_g();
        for(v=max_element(g,g+ptr)-g;v!=-1;v=p[v]){
            used[t[v].id]=1;
            q[++r]=t[v].id;
        }
    }
}

int main(){
    ropen("input.txt");
    wopen("output.txt");
    scanf("%d%d",&k,&n);
    rep(i,n){
        scanf("%d%d",&a[i].bg,&a[i].en);
        if (a[i].bg>a[i].en) swap(a[i].bg,a[i].en);
        a[i].id=i;
        w[i]=b[i]=a[i];
    }
    sort(a,a+n,cmp1);
    sort(b,b+n,cmp2);
    rep(i,n){
        ptr=0;
        rep(j,n) if (b[j].bg>=a[i].bg && b[j].en<=a[i].en && b[j].id!=a[i].id){
            t[ptr].bg=b[j].bg;
            t[ptr].en=b[j].en;
            t[ptr].id=b[j].id;
            t[ptr].ans=f[b[j].id];
            ++ptr;
        }
        calc_g();
        f[a[i].id]=*max_element(g,g+ptr)+1;
    }
    ptr=0;
    rep(j,n){
        t[ptr].bg=b[j].bg;
        t[ptr].en=b[j].en;
        t[ptr].id=b[j].id;
        t[ptr].ans=f[b[j].id];
        ++ptr;
    }
    calc_g();
    printf("%d\n",n-*max_element(g,g+n));
    rec_ans();
    rep(i,n) if (!used[i]) printf("%d ",i+1);
    return 0;
}