#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int n,order[200001],p[200001],cnt;
map <int, int> mp[300001];
vector <int> px,py;
int f(int i){
return (p[i]==i?i:p[i]=f(p[i]));
}
bool unite(int i, int j){
i=f(i);
j=f(j);
if (i==j)
return false;
p[j]=i;
return true;
}
int construct_roads(vector <int> x, vector <int> y){
vector <int32_t> u,v,a,b;
n=x.size();
for (int i=0;i<n;i++)
mp[x[i]][y[i]]=i;
iota(p,p+n,0);
iota(order,order+n,0);
px=x,py=y;
sort(order,order+n,[](int i, int j){return px[i]+py[i]<px[j]+py[j];});
for (int it=0;it<n;it++){
int i=order[it];
if (mp[x[i]].count(y[i]-2)){
int j=mp[x[i]][y[i]-2],X=x[i]+(x[i]+y[i])%4-1,Y=y[i]-1;
if (!mp[X].count(Y)){
u.push_back(i);
v.push_back(j);
cnt+=unite(i,j);
a.push_back(X);
b.push_back(Y);
mp[X][Y]=1;
}
}
if (mp[x[i]-2].count(y[i])){
int j=mp[x[i]-2][y[i]],X=x[i]-1,Y=y[i]+1-(x[i]+y[i])%4;
if (!mp[X].count(Y)){
u.push_back(i);
v.push_back(j);
cnt+=unite(i,j);
a.push_back(X);
b.push_back(Y);
mp[X][Y]=1;
}
}
}
if (cnt<n-1)
return 0;
build(u,v,a,b);
return 1;
}
