#include "parks.h"
#include "bits/stdc++.h"
using namespace std;
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define forn(i, n) for(int i = 0; i < n; ++i)
const int N = 2e5 + 10;
int p[N];
int get(int a) {
return p[a] = (a == p[a] ? a : get(p[a]));
}
bool uni(int a, int b) {
a = get(a), b = get(b);
if(a == b) return false;
p[a] = b;
return true;
}
struct point {
int x, y, idx;
};
bool cmp(point a, point b) {
if(a.x < b.x) return 1;
if(a.x > b.x) return 0;
return a.y < b.y;
}
map<pair<int, int>, int> st, benches;
int construct_roads(vector<int> x, vector<int> y) {
forn(i, N) p[i] = i;
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
vector<int> u, v, a, b;
vector<point> points;
forn(i, sz(x)) points.push_back({x[i], y[i], i}), st[{x[i], y[i]}] = i;
sort(all(points), cmp);
for(auto p: points) {
pair<int, int> c = {p.x - 2, p.y};
if(st.count(c) && get(st[c]) != get(p.idx)) {
if(p.x % 4 == 0) {
if(p.y % 4 == 2) {
a.push_back(p.x - 1);
b.push_back(p.y - 1);
if(benches.count({a.back(), b.back()})) {
a.pop_back();
b.pop_back();
} else {
u.push_back(st[c]), v.push_back(p.idx);
uni(st[c], p.idx);
benches[{a.back(), b.back()}] = 1;
}
} else {
a.push_back(p.x - 1);
b.push_back(p.y + 1);
if(benches.count({a.back(), b.back()})) {
a.pop_back();
b.pop_back();
} else {
u.push_back(st[c]), v.push_back(p.idx);
uni(st[c], p.idx);
benches[{a.back(), b.back()}] = 1;
}
}
} else {
if(p.y % 4 == 2) {
a.push_back(p.x - 1);
b.push_back(p.y + 1);
if(benches.count({a.back(), b.back()})) {
a.pop_back();
b.pop_back();
} else {
u.push_back(st[c]), v.push_back(p.idx);
uni(st[c], p.idx);
benches[{a.back(), b.back()}] = 1;
}
} else {
a.push_back(p.x - 1);
b.push_back(p.y - 1);
if(benches.count({a.back(), b.back()})) {
a.pop_back();
b.pop_back();
} else {
u.push_back(st[c]), v.push_back(p.idx);
uni(st[c], p.idx);
benches[{a.back(), b.back()}] = 1;
}
}
}
}
c = {p.x, p.y - 2};
if(st.count(c) && get(st[c]) != get(p.idx)) {
if(p.y % 4 == 0) {
if(p.x % 4 == 2) {
a.push_back(p.x + 1);
b.push_back(p.y - 1);
if(benches.count({a.back(), b.back()})) {
a.pop_back();
b.pop_back();
} else {
u.push_back(st[c]), v.push_back(p.idx);
uni(st[c], p.idx);
benches[{a.back(), b.back()}] = 1;
}
} else {
a.push_back(p.x - 1);
b.push_back(p.y - 1);
if(benches.count({a.back(), b.back()})) {
a.pop_back();
b.pop_back();
} else {
u.push_back(st[c]), v.push_back(p.idx);
uni(st[c], p.idx);
benches[{a.back(), b.back()}] = 1;
}
}
} else {
if(p.x % 4 == 2) {
a.push_back(p.x - 1);
b.push_back(p.y - 1);
if(benches.count({a.back(), b.back()})) {
a.pop_back();
b.pop_back();
} else {
u.push_back(st[c]), v.push_back(p.idx);
uni(st[c], p.idx);
benches[{a.back(), b.back()}] = 1;
}
} else {
a.push_back(p.x + 1);
b.push_back(p.y - 1);
if(benches.count({a.back(), b.back()})) {
a.pop_back();
b.pop_back();
} else {
u.push_back(st[c]), v.push_back(p.idx);
uni(st[c], p.idx);
benches[{a.back(), b.back()}] = 1;
}
}
}
}
}
for(int i = 0; i < sz(x); ++i) if(get(i) != get(0)) return 0;
build(u, v, a, b);
return 1;
}
