#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define MASK(n) (1LL << n)
#define PhTrNghia "skyscrapers"
using namespace std;
const int maxn = 2e5 + 5;
const int inf = 1e18;
int n, t;
int x[maxn], y[maxn], ans[maxn];
bool used[maxn], visited[maxn];
bool xuat_hien(int u, int v){
for (int i = 1; i <= n; i++) if (!used[i] && x[i] == u && y[i] == v) return 1;
return 0;
}
bool not_cool(int u, int v){ //block 4 direct
return xuat_hien(u + 1, v) && xuat_hien(u - 1, v) && xuat_hien(u, v + 1) && xuat_hien(u, v - 1);
}
bool ok(int i){ //neu remove cai o loz nay di thi co o nao khac bi anh huong ko
int xi = x[i], yi = y[i];
used[i] = 1;
for (int dx = -1; dx <= 1; dx++){
for (int dy = -1; dy <= 1; dy++){
if (!dx && !dy) continue;
int u = xi + dx;
int v = yi + dy;
if (xuat_hien(u, v)){
if (not_cool(u, v)){
used[i] = 0;
return 0;
}
}
}
}
used[i] = 0;
return 1;
}
void dfs(int i){
visited[i] = 1;
for (int j = 1; j <= n; j++) if (!visited[j] && abs(x[i] - x[j]) <= 1 && abs(y[i] - y[j]) <= 1) dfs(j);
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
//if (fopen(PhTrNghia".INP", "r")){
//freopen(PhTrNghia".INP", "r", stdin);
//freopen(PhTrNghia".OUT", "w", stdout);
//}
cin >> n >> t;
for (int i = 1; i <= n; i++) cin >> x[i] >> y[i];
dfs(1);
for (int i = 1; i <= n; i++){
if (!visited[i]){
cout << "NO" << endl;
return 0;
}
}
for (int step = 1; step <= n; step++){
int pick = -1;
for (int i = 1; i <= n; i++){
if (!used[i] && ok(i)){
if (t == 1){
pick = i; //lay me luon
break;
} else if (pick == -1 or i > pick) pick = i; //greedy for t = 2 ?
}
}
if (pick == -1){
cout << "NO" << endl;
return 0;
}
used[pick] = 1;
ans[step] = pick;
}
cout << "YES" << endl;
for (int i = n; i >= 1; i--) cout << ans[i] << endl;
return 0;
}
/*
3
2
0 0
0 1
0 2
3
1
0 0
1 1
2 2
2
1
0 0
0 2
*/
