/////////////////////////////
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define n nnn
typedef array<int,4> arin;
const int N=2e5+1;
int n;
int cx[N],cy[N];
vector<arin>edges;
vector<int>built[4];
int dx[4]={-2,0,2,0};
int dy[4]={0,-2,0,2};
int ex[4]={-1,1,1,-1};
int ey[4]={-1,-1,1,1};
int p[N];
int find(int x){
if(p[x]!=x) p[x]=find(p[x]);
return p[x];
}
bool join(int x,int y){
x=find(x);y=find(y);
if(x==y) return false;
p[x]=y;
return true;
}
map<pair<int,int>,int>mp,sq;
map<pair<int,int>,bool>used;
map<pair<int,int>,bool>ban;
vector<pair<int,pair<int,int> > >adj[N];
bool vis[N];
#define fi first
#define se second
void dfs(int id){
for(auto c:adj[id]){
if(!vis[c.fi]){
vis[c.fi]=true;
ban[c.se]=true;
dfs(c.fi);
}
}
}
vector<pair<pair<int,int>,int> >sqq;
int construct_roads(vector<int>x,vector<int>y){
n=x.size();
for(int i=1; i<=n ;i++){
cx[i]=x[i-1];
cy[i]=y[i-1];
mp[{cx[i],cy[i]}]=i;
p[i]=i;
}
int m=0;
for(int i=1; i<=n ;i++){
if(!mp[{cx[i],cy[i]}]) continue;
if(!mp[{cx[i]+2,cy[i]}]) continue;
if(!mp[{cx[i],cy[i]+2}]) continue;
if(!mp[{cx[i]+2,cy[i]+2}]) continue;
sq[{cx[i]+1,cy[i]+1}]=++m;
}
typedef pair<int,int> pii;
for(auto c:sq) sqq.push_back({c.fi,c.se});
for(auto c:sqq){
auto cur=c.fi;
int c1=mp[(pii){cur.fi-1,cur.se-1}];
int c2=mp[(pii){cur.fi+1,cur.se-1}];
int c3=mp[(pii){cur.fi-1,cur.se+1}];
int c4=mp[(pii){cur.fi+1,cur.se+1}];
if((cur.fi+cur.se)%4==0){//horizontal
int u=sq[{cur.fi-2,cur.se}];
int v=sq[{cur.fi+2,cur.se}];
adj[u].push_back({c.se,{c1,c3}});
adj[v].push_back({c.se,{c2,c4}});
}
else{
int u=sq[{cur.fi,cur.se-2}];
int v=sq[{cur.fi,cur.se+2}];
adj[u].push_back({c.se,{c1,c2}});
adj[v].push_back({c.se,{c3,c4}});
}
}
dfs(0);
for(int i=1; i<=n ;i++){
if((cx[i]+cy[i])%4!=0) continue;
for(int j=0; j<4 ;j++){
int s=mp[{cx[i]+dx[j],cy[i]+dy[j]}];
if(s==0) continue;
if(ban[{i,s}]==1 || ban[{s,i}]==1) continue;
if(join(i,s)){
edges.push_back(arin{i-1,s-1,cx[i]+ex[j],cy[i]+ey[j]});
}
}
}
if(edges.size()!=n-1) return 0;
for(auto c:edges){
for(int j=0; j<4 ;j++){
built[j].push_back(c[j]);
}
}
build(built[0],built[1],built[2],built[3]);
return 1;
}
////////////////////////////////////////////////////////////////////////
