#include "parks.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
struct DSU{
vector<int> e;
DSU(int n){
e=vector<int>(n,-1);
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
int sz(int x){
return -e[find(x)];
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
return true;
}
};
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
map<int,map<int,int>> mp;
int n=(int)x.size();
for(int i=0;i<n;i++){
mp[y[i]][x[i]]=i+1;
}
vector<int> u,v,a,b;
for(int i=0;i<n;i++){
if(mp[y[i]+2][x[i]]!=0){
u.push_back(i);
v.push_back(mp[y[i]+2][x[i]]-1);
if((x[i]+y[i])%4==0){
a.push_back(x[i]-1);
b.push_back(y[i]+1);
}
else{
a.push_back(x[i]+1);
b.push_back(y[i]+1);
}
}
if(mp[y[i]][x[i]+2]!=0){
u.push_back(i);
v.push_back(mp[y[i]][x[i]+2]-1);
if((x[i]+y[i])%4==0){
a.push_back(x[i]+1);
b.push_back(y[i]+1);
}
else{
a.push_back(x[i]+1);
b.push_back(y[i]-1);
}
}
}
DSU dsu(n);
for(int i=0;i<(int)u.size();i++){
dsu.unite(u[i],v[i]);
}
if(dsu.sz(0)!=n) return 0;
build(u,v,a,b);
return 1;
}
