#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int dsu[200010],L,R;
vector <int> g[200010],match1,match2,dist;
int prt(int n){
if (dsu[n]==n) return n;
return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
dsu[prt(u)]=dsu[prt(v)];
}
bool cmp(pair <pair <int,int>,int> u,pair <pair <int,int>,int> v){
if (u.first.second!=v.first.second) return u.first.second<v.first.second;
return u.first.first<v.first.first;
}
map <pair <int,int>,int> mp;
int gt(int x,int y){
if (mp.find({x,y})==mp.end()) return -1;
return mp[{x,y}];
}
int construct_roads(vector <int> x,vector <int> y){
int n=x.size();
pair <pair <int,int>,int> a[n];
for (int i=0; i<n; i++) a[i]={{x[i],y[i]},i};
for (int i=0; i<n; i++) mp[{x[i],y[i]}]=i;
sort(a,a+n);
for (int i=0; i<n; i++) dsu[i]=i;
set <pair <int,int> > s;
for (int i=1; i<n; i++){
if (a[i-1].first.first==a[i].first.first&&a[i-1].first.second+2==a[i].first.second){
s.insert({a[i-1].first.first-1,a[i].first.second-1});
s.insert({a[i-1].first.first+1,a[i].first.second-1});
}
}
sort(a,a+n,cmp);
for (int i=1; i<n; i++){
if (a[i-1].first.first+2==a[i].first.first&&a[i-1].first.second==a[i].first.second){
s.insert({a[i].first.first-1,a[i].first.second-1});
s.insert({a[i].first.first-1,a[i].first.second+1});
}
}
vector <int> u,v,A,B;
for (auto i:s){
if ((i.first+i.second)%4==0){
int tx=gt(i.first-1,i.second+1),ty=gt(i.first+1,i.second+1);
if (tx!=-1&&ty!=-1){
u.push_back(tx); v.push_back(ty); A.push_back(i.first); B.push_back(i.second);
unn(tx,ty);
} else {
tx=gt(i.first-1,i.second-1),ty=gt(i.first+1,i.second-1);
if (tx!=-1&&ty!=-1){
u.push_back(tx); v.push_back(ty); A.push_back(i.first); B.push_back(i.second);
unn(tx,ty);
}
}
} else {
int tx=gt(i.first-1,i.second+1),ty=gt(i.first-1,i.second-1);
if (tx!=-1&&ty!=-1){
u.push_back(tx); v.push_back(ty); A.push_back(i.first); B.push_back(i.second);
unn(tx,ty);
} else {
tx=gt(i.first+1,i.second+1),ty=gt(i.first+1,i.second-1);
if (tx!=-1&&ty!=-1){
u.push_back(tx); v.push_back(ty); A.push_back(i.first); B.push_back(i.second);
unn(tx,ty);
}
}
}
}
for (int i=0; i<n; i++){
if (prt(i)!=prt(0)) return 0;
}
build(u,v,A,B);
return 1;
}
