#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#define debug(x) #x << " = " << x << '\n'
using ll = long long;
const int dx[8] = {-1, 0, +1, 0, -1, -1, +1, +1};
const int dy[8] = {0, -1, 0, +1, -1, +1, -1, +1};
struct Point {
int x, y;
Point() {}
Point(int _x, int _y) : x(_x), y(_y) {}
Point operator + (const Point &other) const {return Point(x + other.x, y + other.y);}
Point operator - (const Point &other) const {return Point(x - other.x, y - other.y);}
void operator += (const Point &other) {*this = *this + other;}
void operator -= (const Point &other) {*this = *this - other;}
friend ll norm(Point P) {
return (ll) P.x * P.x + (ll) P.y * P.y;
}
};
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int n, cer;
std::cin >> n >> cer;
if (cer == 1) {
std::vector<Point> a(n);
std::map<std::pair<int, int>, int> mp;
for (int i = 0; i < n; i++) {
auto &[x, y] = a[i];
std::cin >> x >> y;
mp[{x, y}] = i;
}
std::vector<bool> vis(n, false);
auto dfs = [&](auto &&self, int i) -> void {
vis[i] = true;
auto [x, y] = a[i];
for (int k = 0; k < 8; k++) {
int xx = x + dx[k];
int yy = y + dy[k];
if (mp.count({xx, yy})) {
int j = mp[{xx, yy}];
if (!vis[j]) {
self(self, j);
}
}
}
};
dfs(dfs, 0);
if (std::count(vis.begin(), vis.end(), true) != n) {
std::cout << "NO";
return 0;
}
vis.assign(n, false);
std::vector<int> st;
auto add_neighbours = [&](int i) {
auto [x, y] = a[i];
for (int k = 0; k < 8; k++) {
int xx = x + dx[k], yy = y + dy[k];
if (mp.count({xx, yy})) {
int j = mp[{xx, yy}];
if (!vis[j]) {
st.push_back(j);
}
}
}
};
st.push_back(0);
std::vector<int> order;
while (!st.empty()) {
int i = st.back();
st.pop_back();
if (vis[i]) {
continue;
}
order.push_back(i);
vis[i] = true;
add_neighbours(i);
}
assert((int) order.size() == n);
std::cout << "YES\n";
for (int i : order) {
std::cout << i + 1 << ' ';
}
}
return 0;
}
