//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <assert.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b...);};
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#define ll long long
#define maxn 150005
#define mod 1000000007
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
unordered_map<ll, int> mp;
unordered_set<ll> bfs, cand;
ll h(pii p) {
return (((ll)p.ff)<<30) + p.ss;
}
pii pos[maxn];
bool vis[maxn], out[maxn], art[maxn], used[maxn];
vector<int> adj[maxn];
void dfs(int n) {
int x = pos[n].ff, y = pos[n].ss;
vis[n] = 1;
for (int dx = -1;dx <= 1;dx++) {
for (int dy = -1;dy <= 1;dy++) {
pii to = {x + dx, y + dy};
cand.insert(h(to));
if (dx == 0 && dy == 0) continue;
int v = mp[h(to)];
if (v) {
if (!vis[v]) dfs(v);
adj[n].push_back(v);
}
}
}
}
int ans[maxn], low[maxn], ti[maxn];
int c = 0;
void dfs2(int n, int par, int root) {
vis[n] = 1;
low[n] = ti[n] = c++;
int p = ti[n], chi = 0, val = 0;
for (int v:adj[n]) {
if (used[v]) continue;
if (!vis[v]) {
chi++;
dfs2(v, n, root);
low[n] = min(low[n], low[v]);
val = max(val, low[v]);
} else if (v != par) {
p = min(p, ti[v]);
}
}
if ((n != root && chi && val >= ti[n]) || (n == root && chi > 1)) art[n] = 1;
low[n] = min(low[n], p);
}
int main() {
io
int n, type;
cin >> n >> type;
int mx = 1<<30, my = 1<<30, st = 0;
for (int i = 1;i <= n;i++) {
cin >> pos[i].ff >> pos[i].ss;
mx = min(mx, pos[i].ff);
if (pos[i].ss < my) {
my = pos[i].ss;
st = pos[i].ff;
}
}
for (int i = 1;i <= n;i++) {
pos[i] = {pos[i].ff - mx + 1, pos[i].ss - my + 1};
mp[h(pos[i])] = i;
}
dfs(1);
for (int i = 1;i <= n;i++) {
if (!vis[i]) {
cout << "NO" << endl;
return 0;
}
vis[i] = 0;
}
queue<pii> que;
que.push({st - mx + 1, 0});
bfs.insert(h(que.front()));
for (int it = 0;it < n;it++) {
while (que.size()) {
pii cur = que.front();que.pop();
for (int k = 0;k < 4;k++) {
pii ne = {cur.ff + dir[k][0], cur.ss + dir[k][1]};
ll x = h(ne);
if (ne.ff >= 0 && ne.ss >= 0) {
int v = mp[x];
if (v) out[v] = 1;
else {
if (cand.find(x) != cand.end() && bfs.find(x) == bfs.end()) {
bfs.insert(x);
que.push(ne);
}
}
}
}
}
for (int j = n;j >= 1;j++) art[j] = 0, vis[j] = 0, low[j] = ti[j] = 0;
c = 0;
for (int j = n;j >= 1;j++) {
if (!used[j]) {
dfs2(j, 0, j);
break;
}
}
//pary(art + 1, art + n + 1);
for (int j = n;j >= 1;j++) {
if (!used[j] && !art[j] && out[j]) {
ans[it] = j;
//cout << j<< endl;
que.push(pos[j]);
bfs.insert(h(pos[j]));
used[j] = 1;
break;
}
}
}
cout << "YES" << endl;
for (int i = n - 1;i >= 0;i--) cout << ans[i] << "\n";
}
/*
3
2
0 0
0 1
0 2
9
1
-5 -5
-4 -6
-3 -7
-2 -6
-1 -5
-2 -4
-3 -3
-4 -4
-3 -5
7 1
0 4
0 5
0 3
0 2
0 7
0 1
0 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14668 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14668 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14668 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3916 KB |
ans=NO N=1934 |
| 2 |
Correct |
3 ms |
3916 KB |
ans=NO N=1965 |
| 3 |
Runtime error |
17 ms |
15636 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
14668 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
112 ms |
23240 KB |
ans=NO N=66151 |
| 2 |
Correct |
26 ms |
7004 KB |
ans=NO N=64333 |
| 3 |
Runtime error |
133 ms |
51068 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3916 KB |
ans=NO N=1934 |
| 2 |
Correct |
3 ms |
3916 KB |
ans=NO N=1965 |
| 3 |
Runtime error |
17 ms |
15636 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
