#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;
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);
}
}
vec<pii> sd;
void sd_cmp() {
for (pii x : usd) {
int u = x.fir, v = x.sec;
if (ps[u] > ps[v]) swap(u, v);
if (ps[u].fir != ps[v].fir) {
sd.push_back({ps[u].fir + 1, ps[u].sec - 1});
} else if (ps[u].fir == 2) {
sd.push_back({ps[u].fir - 1, ps[u].sec + 1});
} else {
sd.push_back({ps[u].fir + 1, ps[u].sec + 1});
}
}
}
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();
vec<int> a, b, c, d;
for (pii x : usd)
a.push_back(x.fir - 1), b.push_back(x.sec - 1);
for (pii x : sd)
c.push_back(x.fir), d.push_back(x.sec);
build(a, b, c, d);
return 1;
}
