#include <stdio.h>
#include <string.h>
#define N 150000
int min(int a, int b) { return a < b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int dx[] = { 0, 1, 0, -1, -1, 1, 1, -1 };
int dy[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
int xx[N], yy[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (ii[j] == i_)
j++;
else if (xx[ii[j]] < xx[i_] || xx[ii[j]] == xx[i_] && yy[ii[j]] < yy[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
int ds[N * 8];
int find(int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds[i]));
}
void join(int i, int j) {
i = find(i);
j = find(j);
if (i == j)
return;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
}
int jj[N][8], ta[N], tb[N];
void dfs(int f, int i) {
static int time;
int h;
ta[i] = tb[i] = ++time;
for (h = 0; h < 8; h++) {
int j = jj[i][h];
if (j == -1)
continue;
if (!ta[j]) {
dfs(i * 8 + h, j);
if (tb[j] < ta[i])
join(i * 8 + h, f);
tb[i] = min(tb[i], tb[j]);
} else if (ta[j] < ta[i]) {
join(i * 8 + h, f);
tb[i] = min(tb[i], ta[j]);
}
}
}
int next[N * 4], prev[N * 4], kk[N];
int ok(int i) {
int h, r, j, k;
r = -1;
for (h = 0; h < 8; h++)
if (jj[i / 4][h] != -1) {
if (r == -1)
r = find(i / 4 * 8 + h);
else if (find(i / 4 * 8 + h) != r)
return 0;
}
k = 1;
for (j = next[i]; j != i && j / 4 == i / 4; j = next[j])
k++;
if (j == i)
return 1;
for (j = prev[i]; j / 4 == i / 4; j = prev[j])
k++;
return kk[i / 4] == k;
}
int pq[N], iq[1 + N], cnt;
int lt(int i, int j) { return i > j; }
int p2(int p) {
return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}
void pq_up(int i) {
int p, q, j;
for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_dn(int i) {
int p, q, j;
for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
iq[pq[j] = p] = j;
iq[pq[i] = p] = i;
}
void pq_add(int i) {
if (!pq[i])
pq[i] = ++cnt, pq_up(i);
}
void pq_remove(int i) {
if (pq[i]) {
int j = iq[cnt--];
if (j != i)
pq[j] = pq[i], pq_up(j), pq_dn(j);
pq[i] = 0;
}
}
int pq_first() { return iq[1]; }
int main() {
static int ii[N], hh[N], ii_[N * 4], ans[N];
int n, n_, t, h, i, j, k;
scanf("%d%d", &n, &t);
for (i = 0; i < n; i++) {
scanf("%d%d", &xx[i], &yy[i]);
ii[i] = i;
}
sort(ii, 0, n);
memset(ds, -1, n * 8 * sizeof *ds);
for (h = 0; h < 8; h++)
for (i = 0, j = 0; i < n; i++) {
int x = xx[ii[i]] + dx[h], y = yy[ii[i]] + dy[h];
while (j < n && (xx[ii[j]] < x || xx[ii[j]] == x && yy[ii[j]] < y))
j++;
if (j < n && xx[ii[j]] == x && yy[ii[j]] == y) {
join(ii[i] * 8 + h, ii[j] * 8 + h ^ 2);
jj[ii[i]][h] = ii[j];
} else
jj[ii[i]][h] = -1;
}
dfs(-1, 0);
for (i = 0; i < n; i++)
if (!ta[i]) {
printf("NO\n");
return 0;
}
i = ii[0], h = 0, k = 0;
do {
hh[i] = h, kk[i]++, ii_[k++] = i * 4 + h;
if (jj[i][h + 4] != -1)
i = jj[i][h + 4], h = (h + 3) % 4;
else if (jj[i][h] != -1)
i = jj[i][h];
else
h = (h + 1) % 4;
} while (i != ii[0] || h != 0);
for (h = 0; h < k; h++)
next[ii_[h]] = ii_[(h + 1) % k], prev[ii_[(h + 1) % k]] = ii_[h];
for (h = 0; h < k; h++)
if (ok(ii_[h]))
pq_add(ii_[h] / 4);
else
pq_remove(ii_[h] / 4);
n_ = 0;
while (cnt) {
int i_, j_;
i = pq_first(), pq_remove(i);
ans[n_++] = i;
if (n_ == n)
break;
for (h = 0; h < 8; h++)
if (jj[i][h] != -1)
jj[jj[i][h]][h ^ 2] = -1, jj[i][h] = -1;
i_ = i * 4 + hh[i];
while (i_ / 4 == i)
i_ = prev[i_];
j_ = i * 4 + hh[i];
while (j_ / 4 == i)
j_ = next[j_];
kk[i_ / 4]--, kk[j_ / 4]--;
i = i_ / 4, h = i_ % 4, k = 0;
do {
hh[i] = h, kk[i]++, ii_[k++] = i * 4 + h;
if (jj[i][h + 4] != -1)
i = jj[i][h + 4], h = (h + 3) % 4;
else if (jj[i][h] != -1)
i = jj[i][h];
else
h = (h + 1) % 4;
} while (i != j_ / 4 || h != j_ % 4);
hh[i] = h, kk[i]++, ii_[k++] = i * 4 + h;
for (h = 0; h + 1 < k; h++)
next[ii_[h]] = ii_[h + 1], prev[ii_[h + 1]] = ii_[h];
for (h = 0; h < k; h++)
if (ok(ii_[h]))
pq_add(ii_[h] / 4);
else
pq_remove(ii_[h] / 4);
}
printf("YES\n");
while (n_--)
printf("%d\n", ans[n_] + 1);
return 0;
}
