#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct dsu {
vector<int> e;
int cc=0;
dsu(int n) {
e=vector<int>(n, -1);
cc=n;
}
int get(int x) {
if(e[x]<0)return x;
return e[x]=get(e[x]);
}
bool unite(int x, int y) {
x=get(x),y=get(y);
if(x==y)return false;
if(-e[x] < -e[y]){
swap(x, y);
}
cc--;
e[x]+=e[y];
e[y] = x;
return true;
}
};
int construct_roads(vector<int> x, vector<int> y) {
vector<pair<int,int>> bc;
int n = x.size();
dsu d(n);
map<pair<int,int>, int> mp;
for(int i = 0;i<n;i++) {
mp[{x[i], y[i]}] = i;
bc.push_back({x[i]-1, y[i]-1});
bc.push_back({x[i]-1, y[i]+1});
bc.push_back({x[i]+1, y[i]-1});
bc.push_back({x[i]+1, y[i]+1});
}
vector<int> a, b, c, D;
for(auto [u,v]:bc) {
if((u+v)%4 == 2) {
if(mp.find(pair{u-1, v+1})!=mp.end() and mp.find(pair{u+1, v+1}) != mp.end() and d.unite(mp[{u-1, v+1}], mp[{u+1, v+1}])) {
a.push_back(mp[{u-1, v+1}]);
b.push_back(mp[{u+1, v+1}]);
c.push_back(u);
D.push_back(v);
}
else if(mp.find(pair{u-1, v-1})!=mp.end() and mp.find(pair{u+1, v-1}) != mp.end() and d.unite(mp[{u-1, v-1}], mp[{u+1, v-1}])) {
a.push_back(mp[{u-1, v-1}]);
b.push_back(mp[{u+1, v-1}]);
c.push_back(u);
D.push_back(v);
}
}
else {
if(mp.find(pair{u+1, v+1})!=mp.end() and mp.find(pair{u+1, v-1}) != mp.end() and d.unite(mp[{u+1, v+1}], mp[{u+1, v-1}])) {
a.push_back(mp[{u+1, v+1}]);
b.push_back(mp[{u+1, v-1}]);
c.push_back(u);
D.push_back(v);
}
else if(mp.find(pair{u-1, v-1})!=mp.end() and mp.find(pair{u-1, v+1}) != mp.end() and d.unite(mp[{u-1, v-1}], mp[{u-1, v+1}])) {
a.push_back(mp[{u-1, v-1}]);
b.push_back(mp[{u-1, v+1}]);
c.push_back(u);
D.push_back(v);
}
}
}
if(d.cc!=1)return false;
build(a, b, c, D);
return true;
}
