#include <bits/stdc++.h>
using namespace std;
int const N=2e5+10;
map<pair<int,int>,bool>scr;
map<pair<int,int>,int>pre,ind;
vector<int>req[N]={};
int cnt[N]={};
bool check(int x,int y)
{
int ans=0;
for (int i=-1;i<=1;i++)
{
for (int j=-1;j<=1;j++)
{
if (i!=0&&j!=0) continue;
if (i==0&&j==0) continue;
pair<int,int>f={x+i,y+j};
if (scr.find(f)==scr.end())
ans++;
}
}
return (ans<=1);
}
void ad(pair<int,int>g)
{
vector<pair<int,int>>z;
for (int i=-1;i<=1;i++)
{
for (int j=-1;j<=1;j++)
{
if (i!=0&&j!=0) continue;
if (i==0&&j==0) continue;
pair<int,int>f={g.first+i,g.second+j};
if (scr.find(f)!=scr.end())
z.push_back(f);
}
}
cout<<g.first<<' '<<g.second<<endl;
for (auto i:z)
{
cnt[ind[i]]++;
req[ind[g]].push_back(ind[i]);
}
}
inline void solve()
{
int n,t;
cin>>n>>t;
int r[n],c[n];
for (int i=0;i<n;i++)
{
cin>>r[i]>>c[i];
pre[{r[i],c[i]}]=1;
ind[{r[i],c[i]}]=i+1;
}
pair<int,int>cur={r[n-1],c[n-1]};
vector<int>ans;
priority_queue<pair<int,pair<int,int>>>S;
S.push({ind[cur],cur});
while (S.size())
{
pair<int,pair<int,int>>ft;
ft=S.top();
S.pop();
pair<int,int>g=ft.second;
if (cnt[ind[g]]) continue;
if (scr[g]==1) continue;
scr[g]=1;
ans.push_back(ft.first);
for (auto i:req[ft.first])
cnt[i]--;
for (int i=-1;i<=1;i++)
{
for (int j=-1;j<=1;j++)
{
pair<int,int>f={g.first+i,g.second+j};
if (pre.find(f)!=pre.end()&&!scr[f]&&!cnt[ind[f]])
{
if (check(f.first,f.second))
ad(f);
S.push({ind[f],f});
}
}
}
}
if (ans.size()!=n)
{
cout<<"NO\n";return;
}
reverse(begin(ans),end(ans));
cout<<"YES\n";
for (auto i:ans)
cout<<i<<'\n';
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
