#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct park{
int x, y, i;
};
const int N = 2e5 + 69;
int root[N];
int find(int x){
if (x == root[x]) return x;
return root[x] = find(root[x]);
}
void unite(int x, int y){
x = find(x); y = find(y);
root[x] = y;
}
pair<int, int> f(int x, int y, int d){
if (d == 0){
int add = -1;
if ((x + y) % 4 == 0) add = 1;
return make_pair(x - 1, y + add);
} else {
int add = -1;
if ((x + y) % 4 == 2) add = 1;
return make_pair(x + add, y - 1);
}
}
int construct_roads(vector<int> x, vector<int> y) {
// if (x.size() == 1) {
// build({}, {}, {}, {});
// return 1;
// }
// std::vector<int> u, v, a, b;
// u.push_back(0);
// v.push_back(1);
// a.push_back(x[0]+1);
// b.push_back(y[0]-1);
// build(u, v, a, b);
// return 1;
int n = x.size();
vector <park> a(n);
for (int i = 0; i < n; i++){
a[i].i = i;
a[i].x = x[i];
a[i].y = y[i];
}
vector <int> u, v, u1, v1;
sort(a.begin(), a.end(), [&](park x, park y){
return x.x + x.y < y.x + y.y;
});
set <pair<int, int>> st;
set <pair<int, int>> foun;
map <pair<int, int>, int> mp;
for (auto x : a){
foun.insert({x.x, x.y});
mp[{x.x, x.y}] = x.i;
if (foun.find({x.x - 2, x.y}) != foun.end() && st.find(f(x.x, x.y, 0)) == st.end()){
auto pi = f(x.x, x.y, 0);
st.insert(pi);
u.push_back(x.i);
v.push_back(mp[make_pair(x.x - 2, x.y)]);
u1.push_back(pi.first);
v1.push_back(pi.second);
}
if (foun.find({x.x, x.y - 2}) != foun.end() && st.find(f(x.x, x.y, 1)) == st.end()){
auto pi = f(x.x, x.y, 1);
st.insert(pi);
u.push_back(x.i);
v.push_back(mp[make_pair(x.x, x.y - 2)]);
u1.push_back(pi.first);
v1.push_back(pi.second);
}
}
for (int i = 0; i < n; i++) root[i] = i;
for (int i = 0; i < (int)u.size(); i++){
unite(u[i], v[i]);
}
for (int i = 0; i < n; i++){
if (find(i) != find(0)) return 0;
}
build(u, v, u1, v1);
return 1;
}
