#include<bits/stdc++.h>
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
int main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin >> n;
int t;
cin >> t;
vector<pii> v(n);
for(auto & i : v)
cin >> i.ff >> i.ss;
map<pii,int> mp;
for(int i = 0; i < n; i++){
mp[{v[i].ff,v[i].ss}] = i;
}
vector<int> pai(n);
iota(all(pai),0);
int dx[]{1,0,-1,0}, dy[]{0,1,0,-1};
int dx2[]{-1,-1,-1,0,1,1,1,0}, dy2[]{-1,0,1,1,1,0,-1,-1};
auto find =[&](int id, auto f) -> int {
if(pai[id] == id)
return id;
return pai[id] = f(pai[id],f);
};
int cmp = n;
auto onion =[&](int a, int b) -> void {
a = find(a,find);
b = find(b,find);
if(a != b){
pai[a] = b;
cmp--;
}
};
vector<int> deg(n);
for(int i = 0; i < n; i++){
for(int j = 0; j < 8; j++){
int xi = v[i].ff+dx2[j], yi = v[i].ss+dy2[j];
if(mp.count({xi,yi})){
onion(i,mp[{xi,yi}]);
deg[i]++;
// cout << i << "++\n";
// cout << mp[{xi,yi}] << "++\n";
}
}
}
if(cmp > 1){
cout << "NO\n";
return 0;
}
t = n;
for(int i = 0; i < n; i++){
for(int j = 0; j < 8; j++){
int xi = v[i].ff+dx2[j], yi = v[i].ss+dy2[j];
if(!mp.count({xi,yi})){
mp[{xi,yi}] = t++;
v.push_back({xi,yi});
}
}
}
pai = vector<int>(t);
iota(all(pai),0);
for(int i = n; i < t; i++){
for(int j = 0; j < 4; j++){
int xi = v[i].ff+dx[j], yi = v[i].ss+dy[j];
if(mp.count({xi,yi}) && mp[{xi,yi}] >= n){
onion(i,mp[{xi,yi}]);
}
}
}
vector<int> check(n);
priority_queue<int> pq;
set<pii> passed;
vector<int> reached(n);
auto dfs =[&](int x, int y, auto dfs) -> void {
passed.insert({x,y});
for(int i = 0; i < 4; i++){
int xi = x+dx[i], yi = y+dy[i];
if(!passed.count({xi,yi}) && mp.count({xi,yi})){
int curval = mp[{xi,yi}];
if(curval >= n){
dfs(xi,yi,dfs);
} else {
if(!check[curval]){
check[curval] = 1;
reached[curval] = 1;
pq.push(curval);
}
}
}
}
};
int mn = 0;
for(int i = 1; i < n; i++){
mn = min(mn,i,[&](int a, int b){
return v[a].ff < v[b].ff;
});
}
dfs(v[mn].ff-1,v[mn].ss,dfs);
vector<int> resp;
while(!pq.empty()){
int cur = pq.top();
pq.pop();
if(check[cur] == 2)
continue;
if(deg[cur]>=2){//check comp
bool failed = 0;
for(int i = 1; i < 4; i+=2){
int leftx = v[cur].ff+dx2[i], lefty = v[cur].ss+dy2[i];
int rightx = v[cur].ff+dx2[i+4], righty = v[cur].ss+dy2[i+4];
int k = i+1;
int sum = 0;
while(k != i+4){
int xi = v[cur].ff+dx2[k], yi = v[cur].ss+dy2[k];
sum+=mp[{xi,yi}] < n && check[mp[{xi,yi}]] < 2;
k++;
}
if(sum < deg[cur] && sum > 0 && find(mp[{leftx,lefty}],find) == find(mp[{rightx,righty}],find)){
failed = 1;
break;
}
}
for(int i = 1; i < 8; i+=2){
int xi = v[cur].ff+dx2[i], yi = v[cur].ss+dy2[i];
int nxi = v[cur].ff+dx2[(i+1)%8], nyi = v[cur].ss+dy2[(i+1)%8];
int nnxi = v[cur].ff+dx2[(i+2)%8], nnyi = v[cur].ss+dy2[(i+2)%8];
if(find(mp[{xi,yi}],find) == find(mp[{nnxi,nnyi}],find) && mp[{nxi,nyi}] < n && check[mp[{nxi,nyi}]] < 2){
failed = 1;
break;
}
}
if(failed){
check[cur] = 0;
continue;
}
}
check[cur] = 2;
resp.push_back(cur);
//cout << "push " << cur << '\n';
dfs(v[cur].ff,v[cur].ss,dfs);
for(int i = 0; i < 8; i++){
int xi = v[cur].ff+dx2[i], yi = v[cur].ss+dy2[i];
if(mp[{xi,yi}] < n){
deg[mp[{xi,yi}]]--;
if(!check[mp[{xi,yi}]] && reached[mp[{xi,yi}]])
pq.push(mp[{xi,yi}]), check[mp[{xi,yi}]] = 1;
}
}
for(int i = 0; i < 4; i++){
int xi = v[cur].ff+dx[i], yi = v[cur].ss+dy[i];
if(mp[{xi,yi}] >= n || check[mp[{xi,yi}]] == 2){
onion(cur,mp[{xi,yi}]);
}
}
}
reverse(all(resp));
if(resp.size() == n){
cout << "YES\n";
for(int i : resp)
cout << i + 1 << '\n';
} else cout << "NO\n";
}
