#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
vector<int> u, v, j,k, b,x,y;
set<pair<int,int> >cand;
int dx[4]={1,1,-1,-1};
int dy[4]={-1,1,-1,1};
map<pair<int,int>,int>mp,udh;
bool vis[maxn+2];
int cx[4]={2,-2,0,0};
int cy[4]={0,0,2,-2};
int tot=0;
void dfs(int cur){
vis[cur]=true; tot++;
for(int q=0;q<4;q++){
int nx=x[cur-1]+cx[q],ny=y[cur-1]+cy[q];
if(mp[{nx,ny}] && !vis[mp[{nx,ny}]]){
dfs(mp[{nx,ny}]);
}
}
}
int construct_roads(vector<int> X, vector<int> Y) {
x=X,y=Y;
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
for(int q=0;q<x.size();q++){
for(int w=0;w<4;w++){
int nx=x[q]+dx[w],ny=y[q]+dy[w];
cand.insert({nx,ny});
}
mp[{x[q],y[q]}]=q+1;
}
dfs(1);
if(tot!=x.size())return 0;
for(auto [nx,ny] : cand){
// cout<<nx<<' '<<ny<<endl;
if((nx+ny)%4==0){
int a=mp[{nx-1,ny-1}],b=mp[{nx+1,ny-1}],c=mp[{nx-1,ny+1}],d=mp[{nx+1,ny+1}];
//if(nx==1 && ny==3)cout<<a<<" k "<<b<<' '<<c<<' '<<d<<endl;
if(a && b ){
u.push_back(a-1), v.push_back(b-1);
j.push_back(nx), k.push_back(ny);
//udh[{a,b}]=udh[{b,a}]=1;
}
else if(c && d ){
u.push_back(c-1), v.push_back(d-1);
j.push_back(nx), k.push_back(ny);
//udh[{c,d}]=udh[{d,c}]=1;
}
}
else{
int a=mp[{nx-1,ny-1}],b=mp[{nx-1,ny+1}],c=mp[{nx+1,ny-1}],d=mp[{nx+1,ny+1}];
if(a && b ){
u.push_back(a-1), v.push_back(b-1);
j.push_back(nx), k.push_back(ny);
// udh[{a,b}]=udh[{b,a}]=1;
}
else if(c && d ){
u.push_back(c-1), v.push_back(d-1);
j.push_back(nx), k.push_back(ny);
// udh[{c,d}]=udh[{d,c}]=1;
}
}
}
build(u, v, j, k);
return 1;
}
