#include "parks.h"
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 2e5 + 5;
int component, a[N], dsu[N];
map<int, int> M[N];
vector<int> px, py;
vector<int> edgex, edgey, pointx, pointy;
int getD(int u) {
return dsu[u] < 0 ? u : dsu[u] = getD(dsu[u]);
}
void add(int u, int v, int chair_x, int chair_y) {
int pu = getD(u);
int pv = getD(v);
if (pu == pv) return;
edgex.push_back(u);
edgey.push_back(v);
pointx.push_back(chair_x);
pointy.push_back(chair_y);
if (dsu[pu] > dsu[pv]) swap(pu, pv);
dsu[pu] += dsu[pv];
dsu[pv] = pu;
--component;
}
int construct_roads(vector<int> xxx, vector<int> yyy) {
px = xxx; py = yyy;
int n = component = px.size();
REP(i, 0, n) dsu[i] = -1;
REP(i, 0, n) M[px[i]][py[i]] = i;
REP(i, 0, n) if ((px[i] + py[i]) & 2) {
if (M[px[i]].count(py[i] + 2))
add(i, M[px[i]][py[i] + 2], px[i] - 1, py[i] + 1);
if (M[px[i] + 2].count(py[i]))
add(i, M[px[i] + 2][py[i]], px[i] + 1, py[i] + 1);
}
REP(i, 0, n) if (!((px[i] + py[i]) & 2)) {
if (M[px[i]].count(py[i] + 2)) {
if (!(M[px[i] + 2].count(py[i]) && M[px[i] + 2].count(py[i] + 2)))
add(i, M[px[i]][py[i] + 2], px[i] + 1, py[i] + 1);
}
if (M[px[i] + 2].count(py[i])) {
if (!(M[px[i]].count(py[i] - 2) && M[px[i] + 2].count(py[i] - 2)))
add(i, M[px[i] + 2][py[i]], px[i] + 1, py[i] - 1);
}
}
if (component != 1) return 0;
build(edgex, edgey, pointx, pointy);
return 1;
}
