#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> cons[200001];
int mask_l[200001];
vector<int> u;
vector<int> v;
vector<int> a;
vector<int> b;
struct dsu{
int sz = 0;
vector<int> pr;
int p(int v){
if(pr[v] == v) return v;
return pr[v] = p(pr[v]);
}
bool un(int u,int v){
u = p(u);
v = p(v);
if(u == v){
return 0;
exit(1);
}
pr[u] = v;
sz++;
return 1;
}
} D;
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
D.pr.resize(n);
map<pair<int,int>,int> sol;
for (int i = 0; i < n; ++i)
{
D.pr[i] = i;
}
vector<pair<int,pair<int,int>>> x_d;
vector<pair<int,pair<int,int>>> y_d;
for (int i = 0; i < n; ++i)
{
x_d.push_back({x[i],{y[i],i}});
y_d.push_back({y[i],{x[i],i}});
sol[{x[i],y[i]}] = i;
}
/*for(int i = 0;i < n;i++){
assert(sol.count({x[i],y[i]}) + sol.count({x[i]+2,y[i]})+sol.count({x[i]+2,y[i]+2})+sol.count({x[i],y[i]+2}) < 4);
}*/
sort(x_d.begin(), x_d.end());
sort(y_d.begin(), y_d.end());
for (int i = 1; i < n; ++i)
{
if(x_d[i].first == x_d[i-1].first and x_d[i].second.first-2 == x_d[i-1].second.first){
D.un(x_d[i-1].second.second,x_d[i].second.second);
}
}
for (int i = 1; i < n; ++i)
{
if(y_d[i].first == y_d[i-1].first and y_d[i].second.first-2 == y_d[i-1].second.first){
D.un(y_d[i-1].second.second,y_d[i].second.second);
}
}
if(D.sz != n-1) return 0;
for (int i = 0; i < n; ++i)
{
if(sol.count({x[i],y[i]+2})) {
if((sol.count({x[i],y[i]}) + sol.count({x[i]+2,y[i]})+sol.count({x[i]+2,y[i]+2})+sol.count({x[i],y[i]+2}) == 4) and ((x[i]+y[i])&3)){
}
else{
u.push_back(sol[{x[i],y[i]+2}]);
v.push_back(i);
if((x[i]+y[i])&3) a.push_back(x[i]+1);
else a.push_back(x[i]-1);
b.push_back(y[i]+1);
}
}
if(sol.count({x[i]+2,y[i]})){
if((sol.count({x[i],y[i]}) + sol.count({x[i]+2,y[i]})+sol.count({x[i]+2,y[i]+2})+sol.count({x[i],y[i]+2}) == 4) and ((x[i]+y[i])&3) == 0){
}
else{
u.push_back(sol[{x[i] + 2, y[i]}]);
v.push_back(i);
if ((x[i] + y[i]) & 3) b.push_back(y[i] - 1);
else b.push_back(y[i] + 1);
a.push_back(x[i] + 1);
}
}
}
//if(points.size() != n-1) return 0;
build(u,v,a,b);
return 1;
}
