#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define arr array
#define vec vector
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 2e5 + 5, INF = 1e9;
int n;
arr<pii, N> ps;
map<pii, int> id;
vec<pii> edg;
void edg_cmp() {
for (int u = 1; u <= n; u++) {
vec<pii> dlt = {{-2, 0}, {2, 0}, {0, -2}, {0, 2}};
for (pii x : dlt) {
int a = ps[u].fir + x.fir, b = ps[u].sec + x.sec;
if (!id[{a, b}]) continue;
edg.push_back({u, id[{a, b}]});
}
}
}
struct Dsj {
arr<int, N> prnt, sz;
void intl() {
for (int u = 1; u <= n; u++)
prnt[u] = u, sz[u] = 1;
}
int pr(int u) {
return (prnt[u] == u) ? u : prnt[u] = pr(prnt[u]);
}
bool mrg(int u, int v) {
u = pr(u), v = pr(v);
if (u == v) return false;
prnt[v] = u, sz[u] += sz[v];
return true;
}
} dsj;
vec<pii> usd;
void usd_cmp() {
dsj.intl();
for (pii x : edg) {
int u = x.fir, v = x.sec;
if (!dsj.mrg(u, v)) continue;
usd.push_back(x);
}
}
map<pii, int> sd_id;
vec<pii> sd;
arr<set<int>, N> usd_adj, sd_adj;
void sd_cmp() {
for (int i = 0; i < usd.size(); i++) {
int u = usd[i].fir, v = usd[i].sec;
if (ps[u] > ps[v]) swap(u, v);
vec<pii> nw;
if (ps[u].fir == ps[v].fir) {
nw.push_back({ps[u].fir - 1, ps[u].sec + 1});
nw.push_back({ps[u].fir + 1, ps[u].sec + 1});
} else {
nw.push_back({ps[u].fir + 1, ps[u].sec - 1});
nw.push_back({ps[u].fir + 1, ps[u].sec + 1});
}
for (pii y : nw) {
if (!sd_id.count(y)) {
int j = sd_id.size();
sd_id[y] = j;
sd.push_back(y);
}
usd_adj[i].insert(sd_id[y]);
sd_adj[sd_id[y]].insert(i);
}
}
// for (pii x : usd) cout << x.fir << " " << x.sec << '\n';
// cout << '\n';
// for (pii x : sd) cout << x.fir << " " << x.sec << '\n';
// cout << '\n';
}
set<pii> ord;
vec<pii> cpl;
void cpl_cmp() {
for (int u = 0; u < sd.size(); u++)
ord.insert({sd_adj[u].size(), u});
while (ord.size()) {
int u = ord.begin()->sec; ord.erase(ord.begin());
// cout << u << '\n';
if (sd_adj[u].empty()) continue;
int v = *sd_adj[u].begin();
cpl.push_back({v, u});
for (int w : usd_adj[v]) {
if (!ord.count({sd_adj[w].size(), w})) continue;
ord.erase({sd_adj[w].size(), w});
sd_adj[w].erase(v);
ord.insert({sd_adj[w].size(), w});
}
}
// while (true) {
// int mn = INF;
// for (int u = 0; u < sd.size(); u++) {
// if (sd_adj[u].empty()) continue;
// mn = min(mn, (int) sd_adj[u].size());
// }
// if (mn == INF) break;
// for (int u = 0; u < sd.size(); u++) {
// if (sd_adj[u].size() != mn) continue;
// int v = *sd_adj[u].begin();
// cpl.push_back({v, u});
// sd_adj[u].clear();
// for (int w : usd_adj[v])
// sd_adj[w].erase(v);
// break;
// }
// }
// for (pii x : cpl) cout << x.fir << " " << x.sec << '\n';
}
int construct_roads(vec<int> _x, vec<int> _y) {
n = _x.size();
for (int u = 1; u <= n; u++) {
ps[u] = {_x[u - 1], _y[u - 1]};
id[ps[u]] = u;
}
edg_cmp();
usd_cmp();
if (dsj.sz[dsj.pr(1)] != n) return 0;
sd_cmp();
cpl_cmp();
if (cpl.size() != n - 1) return 0;
vec<int> a, b, c, d;
for (pii x : cpl) {
int u = x.fir, v = x.sec;
a.push_back(usd[u].fir - 1);
b.push_back(usd[u].sec - 1);
c.push_back(sd[v].fir);
d.push_back(sd[v].sec);
}
build(a, b, c, d);
return 1;
}
