#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
map<pair<int, int>, int> mp;
map<pair<int, int>, int>::iterator it;
set<int> st;
int n, scc_cnt, p[maxn], rc[maxn][8], ans[maxn], ans_cnt;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int fp(int x) { return x == p[x] ? x : p[x] = fp(p[x]); }
struct Data {
  int scc, x, y;
  bool full;
} dat[maxn];
bool vis[maxn];
void dfs1(int id) {
  vis[id] = true;
  for (int w = 0; w <= 7; w++)
    if (mp.find(make_pair(dat[id].x + dx[w], dat[id].y + dy[w])) != mp.end()) {
      int to = mp[make_pair(dat[id].x + dx[w], dat[id].y + dy[w])];
      if (!vis[to]) dfs1(to);
    }
}
void dfs2(int id) {
  dat[id].scc = scc_cnt;
  for (int w = 0; w <= 3; w++)
    if (rc[id][w * 2] > n && dat[rc[id][w * 2]].scc == -1) dfs2(rc[id][w * 2]);
}
bool chk(int id) {
  bool flg = false;
  for (int w = 0; w <= 3; w++)
    if (!dat[rc[id][w * 2]].full && !fp(dat[rc[id][w * 2]].scc)) flg = true;
  if (!flg) return false;
  for (int w = 0; w <= 7; w++)
    if (dat[rc[id][w]].full) {
      int rg[8] = {0}, rg_cnt = 0;
      for (int i = (w + 1) % 8; i != w; i = (i + 1) % 8)
        if (!dat[rc[id][i]].full) {
          int j = i;
          rg_cnt++;
          while (!dat[rc[id][(j + 1) % 8]].full)
            rg[j] = rg_cnt, j = (j + 1) % 8;
          rg[j] = rg_cnt;
          i = j;
        }
      for (int w1 = 0; w1 <= 3; w1++)
        for (int w2 = w1 + 1; w2 <= 3; w2++)
          if (!dat[rc[id][w1 * 2]].full && !dat[rc[id][w2 * 2]].full &&
              rg[w1 * 2] != rg[w2 * 2] &&
              fp(dat[rc[id][w1 * 2]].scc) == fp(dat[rc[id][w2 * 2]].scc))
            return false;
      return true;
    }
  return true;
}
vector<int> vec;
void dfs3(int id) {
  dat[id].scc = 0;
  for (int w = 0; w <= 3; w++)
    if (rc[id][w * 2])
      if (dat[rc[id][w * 2]].full)
        vec.push_back(rc[id][w * 2]);
      else if (dat[rc[id][w * 2]].scc)
        dfs3(rc[id][w * 2]);
}
void solve(int id) {
  for (int w = 0; w <= 3; w++)
    if (!dat[rc[id][w * 2]].full && !dat[rc[id][w * 2]].scc) {
      vec.clear();
      dfs3(id);
      for (int i : vec)
        if (chk(i)) st.insert(i);
      return;
    }
  for (int w = 0; w <= 3; w++)
    if (!dat[rc[id][w * 2]].full)
      if (dat[id].scc == -1)
        dat[id].scc = fp(dat[rc[id][w * 2]].scc);
      else
        p[fp(dat[rc[id][w * 2]].scc)] = dat[id].scc;
}
int main() {
  int Num;
  cin >> n >> Num;
  for (int i = 1; i <= n; i++) {
    cin >> dat[i].x >> dat[i].y;
    dat[i].full = true;
    mp[make_pair(dat[i].x, dat[i].y)] = i;
  }
  dfs1(1);
  for (int i = 1; i <= n; i++)
    if (!vis[i]) {
      cout << "NO";
      return 0;
    }
  cout << "YES" << '\n';
  for (int i = 1; i <= n; i++)
    for (int w = 0; w <= 7; w++)
      if (mp.find(make_pair(dat[i].x + dx[w], dat[i].y + dy[w])) == mp.end()) {
        int siz = mp.size() + 1;
        mp[make_pair(dat[i].x + dx[w], dat[i].y + dy[w])] = siz;
        dat[siz].x = dat[i].x + dx[w];
        dat[siz].y = dat[i].y + dy[w];
      }
  for (int id = 1; id <= mp.size(); id++)
    for (int w = 0; w <= 7; w++) {
      int cx = dat[id].x + dx[w], cy = dat[id].y + dy[w];
      if (mp.find(make_pair(cx, cy)) != mp.end())
        rc[id][w] = mp[make_pair(cx, cy)];
    }
  for (int i = 1; i <= mp.size(); i++) dat[i].scc = -1;
  scc_cnt = -1;
  for (it = mp.begin(); it != mp.end(); it++)
    if (it->second > n && dat[it->second].scc == -1) {
      p[++scc_cnt] = scc_cnt;
      dfs2(it->second);
    }
  for (int i = 1; i <= n; i++)
    if (chk(i)) st.insert(i);
  while (!st.empty()) {
    int id = *st.rbegin();
    st.erase(id);
    if (!chk(id)) continue;
    ans[++ans_cnt] = id;
    dat[id].full = false;
    solve(id);
    for (int w = 0; w <= 7; w++)
      if (dat[rc[id][w]].full && chk(rc[id][w])) st.insert(rc[id][w]);
  }
  for (int i = n; i; i--) cout << ans[i] << '\n';
  return 0;
}
