#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5;
int n, T;
int r[nmax + 5], c[nmax + 5];
bool sel[nmax + 5];
map<pair<int,int>, int> t;
int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
void dfs_check(int nod)
{
sel[nod] = true;
int x = r[nod];
int y = c[nod];
for(int p=0; p<8; p++)
{
int xx = x + dx[p];
int yy = y + dy[p];
int son = t[ {xx, yy}];
if(son == 0)
{
continue;
}
if(sel[son])
{
continue;
}
dfs_check(son);
}
}
void solve1()
{
int poz = 1;
for(int i=1; i<=n; i++)
{
if(r[i] < r[poz] || (r[i] == r[poz] && c[i] < c[poz]))
{
poz = i;
}
}
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> h;
h.push({r[poz], c[poz]});
sel[poz] = true;
vector<int> rez;
while(!h.empty())
{
int x = h.top().first;
int y = h.top().second;
int nod = t[ {x, y}];
h.pop();
rez.push_back(nod);
for(int p=0; p<8; p++)
{
int xx = x + dx[p];
int yy = y + dy[p];
int son = t[ {xx, yy}];
if(son == 0)
{
continue;
}
if(sel[son])
{
continue;
}
sel[son] = true;
h.push({r[son], c[son]});
}
}
cout<<"YES\n";
for(auto it : rez)
{
cout<<it<<'\n';
}
}
map<pair<int,int>,bool> w, reach, lib;
vector<pair<int,int>> lst;
bool used[nmax + 5];
int l[nmax + 5], lvl[nmax + 5];
bool crit[nmax + 5];
void bfs()
{
queue<pair<int,int>> q;
for(auto it : lst)
{
q.push(it);
}
while(!q.empty())
{
int x = q.front().first;
int y = q.front().second;
q.pop();
for(int p=0; p<4; p++)
{
int xx = x + dx[p];
int yy = y + dy[p];
if(!w[ {xx, yy}] || reach[{xx, yy}])
{
continue;
}
if(t[ {xx, yy}] && !used[t[ {xx, yy}]])
{
reach[{xx, yy}] = true;
}
else
{
reach[{xx, yy}] = true;
q.push({xx, yy});
}
}
}
}
void dfs(int nod, int from = 0)
{
crit[nod] = false;
lvl[nod] = 1 + lvl[from];
l[nod] = lvl[nod];
int x = r[nod];
int y = c[nod];
sel[nod] = true;
for(int p=0; p<8; p++)
{
int xx = x + dx[p];
int yy = y + dy[p];
int son = t[ {xx, yy}];
if(son == 0 || used[son])
{
continue;
}
if(sel[son])
{
l[nod] = min(l[nod], lvl[son]);
}
else
{
dfs(son, nod);
l[nod] = min(l[nod], l[son]);
if(l[son] >= lvl[nod])
{
crit[nod] = true;
}
}
}
}
void solve2()
{
for(int i=1; i<=n; i++)
{
int x = r[i];
int y = c[i];
w[ {x, y}] = true;
for(int p=0; p<8; p++)
{
int xx = x + dx[p];
int yy = y + dy[p];
if(t[ {xx, yy}])
{
continue;
}
w[ {xx, yy}] = true;
lib[ {xx, yy}] = true;
for(int j=xx; j<=xx+n; j++)
{
if(t[ {j, yy}])
{
lib[ {xx, yy}] = false;
break;
}
}
if(lib[ {xx, yy}])
{
continue;
}
lib[ {xx, yy}] = true;
for(int j=xx-n; j<=xx; j++)
{
if(t[ {j, yy}])
{
lib[ {xx, yy}] = false;
break;
}
}
if(lib[ {xx, yy}])
{
continue;
}
lib[ {xx, yy}] = true;
for(int j=yy; j<=yy+n; j++)
{
if(t[ {xx, j}])
{
lib[ {xx, yy}] = false;
break;
}
}
if(lib[ {xx, yy}])
{
continue;
}
lib[ {xx, yy}] = true;
for(int j=yy-n; j<=yy; j++)
{
if(t[ {xx, j}])
{
lib[ {xx, yy}] = false;
break;
}
}
if(lib[ {xx, yy}])
{
continue;
}
}
for(int p=0; p<8; p++)
{
int xx = x + dx[p];
int yy = y + dy[p];
if(lib[ {xx, yy}])
{
lst.push_back({xx, yy});
}
}
}
vector<int> rez(n + 1);
for(int i=n; i>=1; i--)
{
reach.clear();
bfs();
for(int j=1; j<=n; j++)
{
sel[j] = false;
}
for(int j=1; j<=n; j++)
{
if(!used[j])
{
dfs(j);
break;
}
}
for(int val=n; val>=1; val--)
{
if(used[val] || crit[val] || !reach[ {r[val], c[val]}])
{
continue;
}
rez[i] = val;
used[val] = true;
}
}
cout<<"YES\n";
for(int i=1; i<=n; i++)
{
cout<<rez[i]<<'\n';
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef home
freopen("nr.in","r",stdin);
freopen("nr.out","w",stdout);
#endif
cin>>n;
cin>>T;
for(int i=1; i<=n; i++)
{
cin>>r[i]>>c[i];
t[ {r[i], c[i]}] = i;
}
dfs_check(1);
for(int i=1; i<=n; i++)
{
if(!sel[i])
{
cout<<"NO\n";
return 0;
}
sel[i] = false;
}
if(T == 1)
{
solve1();
}
else
{
solve2();
}
return 0;
}
