#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int,int>,int>mapa;
int roza[4][2] = {{0,-2}, {0,2}, {-2,0}, {2,0}};
int father[200010];
int find(int x){
if(father[x]==x)return x;
return father[x] = find(father[x]);
}
int construct_roads(vector<int> x, vector<int> y) {
vector<int>va,vb,vu,vv;
int n = x.size(), i;
vector<pair<int,int>>p;
for(i=0;i<n;i++){
mapa[{x[i],y[i]}]=i;
p.push_back({x[i], y[i]});
}
sort(p.begin(), p.end());
for(i=0;i<n;i++)father[i] = i;
for(int j = 0;j<n;j++){
i = mapa[p[j]];
if(mapa.find({x[i],y[i]})!=mapa.end() && mapa.find({x[i]+2, y[i]})!=mapa.end() && mapa.find({x[i], y[i]+2})!=mapa.end() && mapa.find({x[i]+2, y[i]+2})!=mapa.end()){
// printf("znalazlem\n");
int a=mapa[{x[i],y[i]}];
int b=mapa[{x[i]+2,y[i]}];
int c=mapa[{x[i],y[i]+2}];
int d=mapa[{x[i]+2,y[i]+2}];
if((x[i]+y[i]+2)%4==2){
if(find(a)!=find(c)){
vu.push_back(a);
vv.push_back(c);
father[find(a)]=find(c);
va.push_back(x[i]-1);
vb.push_back(y[i]+1);
}
if(find(b)!=find(d)){
vu.push_back(b);
vv.push_back(d);
father[find(b)]=find(d);
va.push_back(x[i]+3);
vb.push_back(y[i]+1);
}
if(find(a)!=find(b)){
vu.push_back(a);
vv.push_back(b);
father[find(a)] = find(b);
va.push_back(x[i]+1);
vb.push_back(y[i]+1);
}
}
else{
if(find(a)!=find(b)){
vu.push_back(a);
vv.push_back(b);
father[find(a)]=find(b);
va.push_back(x[i]+1);
vb.push_back(y[i]-1);
}
if(find(c)!=find(d)){
vu.push_back(c);
vv.push_back(d);
father[find(c)]=find(d);
va.push_back(x[i]+1);
vb.push_back(y[i]+3);
}
if(find(a)!=find(c)){
vu.push_back(a);
vv.push_back(c);
father[find(a)] = find(c);
va.push_back(x[i]+1);
vb.push_back(y[i]+1);
}
}
}
}
for(int ij=0;ij<n;ij++){
i = mapa[p[ij]];
for(auto j: roza){
if(mapa.find({x[i]+j[0], y[i]+j[1]})!=mapa.end()){
if(find(i)==find(mapa[{x[i]+j[0], y[i]+j[1]}]))continue;
father[find(i)] = find(mapa[{x[i]+j[0], y[i]+j[1]}]);
vu.push_back(mapa[{x[i]+j[0], y[i]+j[1]}]);
vv.push_back(i);
int A = x[i]+j[0]/2, B = y[i]+j[1]/2;
//printf("%d %d\n", A, B);
if(j[1]==0){
if((A+B)%4==1)
va.push_back(A),vb.push_back(B+1);
else
va.push_back(A),vb.push_back(B-1);
}
else{
if((A+B)%4==1)
va.push_back(A-1),vb.push_back(B);
else
va.push_back(A+1),vb.push_back(B);
}
}
}
}
for(i=0;i<n;i++)
if(find(i)!=find(0))return 0;
build(vu,vv,va,vb);
return 1;
}
