// created:  2024-09-27 15:29:34
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<queue>
#include<vector>
#define F(i,l,r) for(int i=(l),i##_end=(r);i<i##_end;++i)
#define I128 //||is_same<T,__int128_t>::value||is_same<T,__uint128_t>::value
using namespace std;
template<typename T>enable_if_t<is_integral<T>::value I128,void> readmain(T &x)
{
	bool neg=false;int c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')neg=true;
	for(x=0;isdigit(c);c=getchar())x=(T)(10*x+(c-'0'));
	if(neg)x=-x;
}
template<typename T>T& read(T &x){readmain(x);return x;}
template<typename T,typename ...Tr>void read(T &x,Tr&... r){readmain(x);read(r...);}
constexpr int N=5005,M=15005;
struct point
{
	int x,y,z;
}c[M],cc[M];
int n,b[N],m,a[M],px[N],py[N],mx,my;
char pre[N][N],st[N][N],vis[N][N];
bool inq[M];
vector<int> adj[M];
priority_queue<int,vector<int>,greater<int>> pq;
bool dfs1(int x,int y,char p=0)
{
	if(y<0||y>=b[x])return true;
	if(vis[x][y])return false;
	vis[x][y]=1;
	if(dfs1(x+1,y,1)||dfs1(x+1,y-1,2)||dfs1(x,y-1,3))return pre[x][y]=p,st[x][y]=2,true;
	return false;
}
void dfs3(int x,int y);
void dfs2(int x,int y)
{
	if(y<0||y>=b[x])return;
	if(vis[x][y]&1)return;
	vis[x][y]|=1;
	if(pre[x][y])dfs3(x-(pre[x][y]!=3),y+(pre[x][y]!=1));
	if(st[x][y]&1)dfs3(x,y);
}
void dfs3(int x,int y)
{
	if(vis[x][y]&2)return;
	vis[x][y]|=2;
	if(st[x][y]&2)dfs2(x,y);
	dfs2(x+1,y);
	dfs2(x+1,y-1);
	dfs2(x,y-1);
}
int main()
{
	int lim;
	read(n,lim);
	F(i,0,n)
	{
		read(c[i].x,c[i].y);--c[i].x,--c[i].y;
		st[c[i].x][c[i].y]=1;
		vis[c[i].x][c[i].y]=1;
		b[c[i].x]=max(b[c[i].x],c[i].y+1);
	}
	for(int i=n;~--i;)b[i]=max(b[i],b[i+1]);
	F(i,0,n)F(j,0,b[i])st[i][j]^=1;
	for(int i=n;--i;)if(b[i])dfs1(i,b[i]-1);
	for(int i=b[0];~--i;)dfs1(0,i);
	F(i,0,n)memset(vis[i],0,b[i]);
	for(int i=n;--i;)if(b[i])dfs2(i,b[i]-1);
	for(int i=b[0];~--i;)dfs2(0,i);
	m=n;
	F(i,0,n)F(j,0,b[i])if(st[i][j]==2&&vis[i][j]==1)c[m++]={i,j,0};
	auto cmpx=[](const point &u,const point &v){return u.x!=v.x?u.x<v.x:u.y<v.y;};
	auto cmpy=[](const point &u,const point &v){return u.y!=v.y?u.y<v.y:u.x<v.x;};
	sort(c,c+m,cmpx);
	F(i,0,m)c[i].z=i;
	memcpy(cc,c,sizeof(point)*m);
	F(i,1,m)
	{
		point &e=*lower_bound(c,c+m,point({c[i].x-1,c[i].y,0}),cmpx);
		if(e.x==c[i].x-1)adj[e.z].emplace_back(c[i].z);
	}
	sort(c,c+m,cmpy);
	F(i,1,m)
	{
		point &e=*lower_bound(c,c+m,point({c[i].x,c[i].y-1,0}),cmpy);
		if(e.y==c[i].y-1)adj[e.z].emplace_back(c[i].z);
	}
	memcpy(c,cc,sizeof(point)*m);
	pq.emplace(0);
	inq[0]=true;
	m=0;
	mx=my=-1;
	while(!pq.empty())
	{
		int u=pq.top();pq.pop();
		for(int v:adj[u])if(!inq[v])inq[v]=true,pq.emplace(v);
		int p=0;
		if(c[u].x)p=px[c[u].x-1]+1;
		if(c[u].y<=my)p=max(p,py[c[u].y]+1);
		mx=max(mx,c[u].x);
		my=max(my,c[u].y);
		memmove(a+p+1,a+p,sizeof(int)*(m-p));
		a[p]=m++;
		px[c[u].x]=p;py[c[u].y]=p;
		F(i,c[u].x+1,mx+1)++px[i];
		F(i,0,c[u].y)++py[i];
	}
	printf("%d\n",m);
	F(i,0,m)printf("%d ",a[i]+1);
	puts("");
	return 0;
}