#include<bits/stdc++.h>
using namespace std;
#define Pii pair<int,int>
#define fir first
#define sec second
const int N=2e6+5;
int n,typ,ans[N];
Pii a[N];

int fx4[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int fx8[8][2]={{-1,-1},{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1}};
int pre4[N][4],pre8[N][8];

map <Pii,int> black;
bool vis[N];
void dfs(int u){
	if(vis[u]) return ;
	vis[u]=1;
	int x=a[u].fir,y=a[u].sec;
	for(int t=0;t<8;t++){
		int v=black[make_pair(x+fx8[t][0],y+fx8[t][1])];
		if(v) dfs(v);
	}
}

map <Pii,int> mp;
Pii p[N];
int id,bla[N];

int fa[N];
int getf(int x){
	if(x==fa[x]) return x;
	return fa[x]=getf(fa[x]);
}
void merge(int x,int y){
	int fx=getf(x),fy=getf(y);
	if(fx==fy) return ;
	fa[fx]=fy;
}

int rgtmost;
set <int> S;
bool check(int u){
	bool fl=0;
	for(int t=0;t<4 && !fl;t++){
		int v=pre4[u][t];
		if(v && !bla[v] && getf(v)==getf(rgtmost)) fl=1;
	}
	if(!fl) return 0;
	
	bool col[8];
	int num[8];
	for(int t=0;t<8;t++){
		int v=pre8[u][t];
		num[t]=v;
		col[t]=(bla[v]>0);
	}
	if(getf(num[1])==getf(num[5]) && (col[2] || col[3] || col[4]) && (col[6] || col[7] || col[0])) return 0;
	if(getf(num[3])==getf(num[7]) && (col[0] || col[1] || col[2]) && (col[4] || col[5] || col[6])) return 0;
	
	if(getf(num[1])==getf(num[3]) && col[2] && (col[4] || col[5] || col[6] || col[7] || col[0])) return 0;
	if(getf(num[3])==getf(num[5]) && col[4] && (col[6] || col[7] || col[0] || col[1] || col[2])) return 0;
	if(getf(num[5])==getf(num[7]) && col[6] && (col[0] || col[1] || col[2] || col[3] || col[4])) return 0;
	if(getf(num[7])==getf(num[1]) && col[0] && (col[2] || col[3] || col[4] || col[5] || col[6])) return 0;
	return 1;
}

void upd(int u){
	for(int t=0;t<8;t++){
		int v=pre8[u][t];
		
		if(v && bla[v]){
			int num=bla[v];
			if(S.find(num)!=S.end()) S.erase(num);
			if(check(v)) S.insert(num);
		}
	}
}
bool viss[N];
void dfss(int u){
	if(viss[u]) return ;
	viss[u]=1;
	upd(u);
	for(int t=0;t<4;t++){
		int v=pre4[u][t];
		if(v && !bla[v]) dfss(v);
	}
}

void add(int u){
	if(p[u].fir>p[rgtmost].fir) rgtmost=u;
	
	for(int t=0;t<4;t++){
		int v=pre4[u][t];
		if(v && !bla[v]) merge(u,v);
	}
	for(int t=0;t<4;t++){
		int v=pre4[u][t];
		if(v && !bla[v] && getf(u)==getf(rgtmost)) dfss(u);
	}
	upd(u);
}

int main(){
	cin>>n>>typ;
	for(int i=1;i<=n;i++){
		int x,y; scanf("%d%d",&x,&y);
		a[i]=make_pair(x,y);
		
		black[make_pair(x,y)]=i;
		mp[make_pair(x,y)]=i;
		for(int t=0;t<8;t++){
			int nx=x+fx8[t][0],ny=y+fx8[t][1];
			mp[make_pair(nx,ny)]=1;
		}
	}
	dfs(1);
	for(int i=1;i<=n;i++)
		if(!vis[i]) return puts("NO"),0;
	
	for(auto x: mp){
		Pii pnt=x.fir;
		p[++id]=pnt; mp[pnt]=id;
	}
	for(int i=1;i<=n;i++) bla[mp[a[i]]]=i;
	
	for(int i=1;i<=id;i++){
		int x=p[i].fir,y=p[i].sec;
		for(int t=0;t<4;t++){
			int nx=x+fx4[t][0],ny=y+fx4[t][1];
			pre4[i][t]=mp[make_pair(nx,ny)];
		}
		for(int t=0;t<8;t++){
			int nx=x+fx8[t][0],ny=y+fx8[t][1];
			pre8[i][t]=mp[make_pair(nx,ny)];
		}
	}
	
	for(int i=1;i<=id;i++) fa[i]=i;
	for(int u=1;u<=id;u++){
		if(bla[u]) continue;
		if(!rgtmost || p[u].fir>p[rgtmost].fir) rgtmost=u;
		
		for(int t=0;t<4;t++){
			int v=pre4[u][t];
			if(v && !bla[v]){
				merge(u,v);
			}
		}
	}
	
	for(int u=1;u<=id;u++){
		if(bla[u]) continue;
		add(u);
	}
	
	for(int t=1;t<=n;t++){
		while(1){
			int num=*(--S.end()); S.erase(num);
			int u=mp[a[num]];
			if(check(u)){
				ans[t]=num;
				bla[u]=0;
				add(u);
				break;
			}
			else S.erase(num);
		}
	}
	
	puts("YES");
	for(int i=n;i>=1;i--) cout<<ans[i]<<'\n';
}