#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
struct query
{
int v,a,b;
};
vi graph8[1200001];
vi graph4[1200001];
map<pii,int> point;
pii poz[120001];
bool used[120001];
bool can_out[120001];
bool odw[120001];
bool full[120001];
int comp[1200001];
vi comp_list[1200001];
vector<query> queries[1200001];
int max_on_x[150003];
int max_on_y[150003];
int min_on_x[150003];
int min_on_y[150003];
vector<pii> dir8 = {{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1},{1,0},{1,1},{0,1}};
vector<pii> dir4 = {{0,1},{0,-1},{1,0},{-1,0}};
vi upd_queue;
set<int> good_points;
void dfs(int v)
{
used[v] = true;
forall(it,graph8[v])
{
if(!used[it] && full[it])
{
dfs(it);
}
}
}
void union_(int a, int b)
{
if(comp[a] == comp[b]) return;
a = comp[a];
b = comp[b];
if(can_out[a] != can_out[b])
{
if(can_out[a])
{
forall(it,comp_list[b])
{
can_out[it] = 1;
}
}
else
{
forall(it,comp_list[b])
{
can_out[it] = 1;
}
}
}
if(siz(comp_list[comp[a]]) > siz(comp_list[b])) swap(a,b);
forall(it,queries[a])
{
if(comp[it.b] == b)
{
upd_queue.pb(it.v);
}
else
{
queries[b].pb(it);
}
}
forall(it,comp_list[a])
{
comp[it] = b;
comp_list[b].pb(it);
}
}
void upd_art(int v, bool first = false)
{
int start = -1;
int ind = 0;
forall(it,graph8[v])
{
if(full[it]) start = ind;
ind++;
}
if(start == -1)
{
good_points.insert(v);
return;
}
// cout << "xd\n";
vi segs;
int pop = -1;
int siz_ = 0;
rep(i,8)
{
start++;
if(start == 8) start = 0;
// cout << start << " " << graph8[v][start] << " g\n";
if(full[graph8[v][start]])
{
if(pop != -1)
{
if(siz_ > 1 || pop % 2 == 1)
{
segs.pb(graph8[v][pop]);
}
}
pop = -1;
}
else
{
siz_++;
pop = start;
}
}
// cout << "xd\n";
if(pop != -1)
{
if(siz_ > 1 || pop % 2 == 1)
{
segs.pb(graph8[v][pop]);
}
}
bool is_ok = true;
// cout << "xd\n";
forall(it1,segs)
{
forall(it2,segs)
{
if(it1 == it2) continue;
if(comp[it1] == comp[it2])
{
is_ok = false;
}
else if(first)
{
queries[comp[it1]].pb({v,it1,it2});
queries[comp[it2]].pb({v,it2,it1});
}
}
}
if(is_ok && can_out)
{
if(used[v])
good_points.insert(v);
}
else if(good_points.find(v) != good_points.end())
{
good_points.erase(good_points.find(v));
}
}
void make_union(int a, int b)
{
union_(a,b);
while(!upd_queue.empty())
{
upd_art(upd_queue.back());
upd_queue.pop_back();
}
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n,t;
cin >> n >> t;
vi ans(n);
vector<pii> points = {{0,0}};
int min_x = 1e9+1;
int min_y = 1e9+1;
rep2(i,1,n)
{
int x,y;
cin >> x >> y;
min_x = min(min_x,x);
min_y = min(min_y,y);
points.pb({x,y});
}
rep2(i,1,n)
{
points[i].ff -= min_x - 1;
points[i].ss -= min_y - 1;
point[points[i]] = i;
poz[i] = points[i];
full[i] = 1;
}
int cur_point = n+1;
rep2(i,1,n)
{
forall(it,dir8)
{
if(point[{points[i].ff+it.ff,points[i].ss+it.ss}] == 0)
{
point[{points[i].ff+it.ff,points[i].ss+it.ss}] = cur_point++;
points.pb({points[i].ff+it.ff,points[i].ss+it.ss});
}
// cout << i << " " << point[{points[i].ff+it.ff,points[i].ss+it.ss}] << " i\n";
graph8[i].pb(point[{points[i].ff+it.ff,points[i].ss+it.ss}]);
if(point[{points[i].ff+it.ff,points[i].ss+it.ss}] > n) graph8[point[{points[i].ff+it.ff,points[i].ss+it.ss}]].pb(i);
}
forall(it,dir4)
{
graph4[point[{points[i].ff+it.ff,points[i].ss+it.ss}]].pb(i);
graph4[i].pb(point[{points[i].ff+it.ff,points[i].ss+it.ss}]);
}
}
dfs(1);
rep2(i,1,n)
{
if(!used[i])
{
cout << "NO\n";
return 0;
}
}
rep2(x,0,150002)
{
max_on_x[x] = -1e9;
max_on_y[x] = -1e9;
min_on_x[x] = 1e9;
min_on_y[x] = 1e9;
}
rep2(i,1,cur_point-1)
{
comp[i] = i;
comp_list[i] = {i};
max_on_x[points[i].ff] = max(points[i].ss,max_on_x[points[i].ff]);
min_on_x[points[i].ff] = min(points[i].ss,min_on_x[points[i].ff]);
max_on_y[points[i].ss] = max(points[i].ff,max_on_y[points[i].ss]);
min_on_y[points[i].ss] = min(points[i].ff,min_on_y[points[i].ss]);
}
rep2(i,1,cur_point-1)
{
if(points[i].ff == max_on_y[points[i].ss] || points[i].ff == min_on_y[points[i].ss])
{
can_out[i] = 1;
}
if(points[i].ss == max_on_x[points[i].ff] || points[i].ss == min_on_x[points[i].ff])
{
can_out[i] = 1;
}
}
rep2(i,1,cur_point-1)
{
if(full[i]) continue;
forall(it,graph4[i])
{
if(!full[it]) make_union(it,i);
}
}
rep2(i,1,n)
{
// cout << i << " upd\n";
upd_art(i,1);
}
for(int i = n-1; i >= 0; i--)
{
auto g = good_points.end();
g--;
int best = *g;
// cout << best << " best\n";
ans[i] = best;
good_points.erase(good_points.find(best));
used[best] = 0;
full[best] = 0;
forall(it,graph4[best])
{
if(!full[it]) make_union(best,it);
}
forall(it,graph8[best])
{
if(full[it]) upd_art(it);
}
}
cout << "YES\n";
forall(it,ans) cout << it << "\n";
}
