/// @author Camillus
#include "bits/stdc++.h"
using ll = long long;
using namespace std;
struct dsu {
vector<int> p;
dsu() = default;
dsu(int n) {
p.resize(n);
iota(p.begin(), p.end(), 0);
}
int get(int x) {
if (x == p[x]) {
return x;
} else {
return p[x] = get(p[x]);
}
}
void join(int x, int y) {
x = get(x);
y = get(y);
p[x] = y;
}
};
auto sideN(int x, int y) {
array<pair<int, int>, 4> result;
result[0] = pair(x, y - 1);
result[1] = pair(x, y + 1);
result[2] = pair(x - 1, y);
result[3] = pair(x + 1, y);
return result;
}
auto sideN(const pair<int, int> &pos) {
return sideN(pos.first, pos.second);
}
auto cornerN(int x, int y) {
array<pair<int, int>, 8> result;
// sides
result[0] = pair(x, y - 1);
result[1] = pair(x, y + 1);
result[2] = pair(x - 1, y);
result[3] = pair(x + 1, y);
// corners
result[4] = pair(x + 1, y + 1);
result[5] = pair(x + 1, y - 1);
result[6] = pair(x - 1, y + 1);
result[7] = pair(x - 1, y - 1);
return result;
}
auto cornerN(const pair<int, int> &pos) {
return cornerN(pos.first, pos.second);
}
ll dist(const pair<int, int> &first, const pair<int, int> &second) {
ll x = first.first - second.first;
ll y = first.second - second.second;
return x * x + y * y;
}
mt19937 rnd(228);
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, t;
cin >> n >> t;
vector<pair<int, int>> a(n);
map<pair<int, int>, int> b;
for (int i = 0; i < n; i++) {
int r, c;
cin >> r >> c;
a[i] = pair(r, c);
b[pair(r, c)] = i;
}
dsu D(n);
for (auto [pos_u, u] : b) {
for (auto pos_v : cornerN(pos_u)) {
if (b.count(pos_v)) {
int v = b[pos_v];
D.join(u, v);
}
}
}
for (int u = 0; u < n; u++) {
if (D.get(u) != D.get(0)) {
cout << "NO\n";
return 0;
}
}
cout << "YES\n";
vector<int> ans;
int start = rnd() % n;
vector<bool> used(n);
set<pair<int, int>> Q;
used[start] = true;
Q.emplace(0, start);
while (!Q.empty()) {
int u = Q.begin()->second;
ans.push_back(u);
Q.erase(Q.begin());
auto pos_u = a[u];
for (auto pos_v : cornerN(pos_u)) {
if (b.count(pos_v)) {
int v = b[pos_v];
if (!used[v]) {
used[v] = true;
Q.emplace(dist(pos_v, a[start]), v);
}
}
}
}
for (int i = 0; i < n; i++) {
cout << ans[i] + 1 << '\n';
}
return 0;
}
