#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(); } }