#include "parks.h"
#include <bits/stdc++.h>
#define ll int
#define vll vector<ll>
#define fr first
#define sc second
#define pb push_back
#define sz size()
#define bc back()
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e5+5;
const int inf=1e9;
ll p[N],siz[N];
map<pair<ll,ll>,bool> vis;
map<pair<ll,ll>,ll> f;
ll anc(ll a){
return (p[a]==a ? a : p[a]=anc(p[a]));
}
bool uni(ll a,ll b){
a=anc(a);
b=anc(b);
if(a==b)return false;
if(siz[a]>siz[b])swap(a,b);
p[a]=b;
siz[b]+=siz[a];
return true;
}
int construct_roads(vector<int> x, vector<int> y) {
vis[{x[0],y[0]}]=1;
vector<pair<ll,pair<ll,ll>>> ver,hor;
ll n=x.size();
ll i;
for(i=0;i<(int)x.size();i++){
f[{x[i],y[i]}]=i+1;
}
for(i=0;i<n;i++){
p[i]=i;
siz[i]=1;
if(f[{x[i]+2,y[i]+0}]){
hor.pb({x[i],{i,f[{x[i]+2,y[i]+0}]-1}});
}if(f[{x[i]+0,y[i]+2}]){
ver.pb({x[i],{i,f[{x[i]+0,y[i]+2}]-1}});
}
}
sort(all(ver));
sort(all(hor));
vll U,V,A,B;
while(ver.sz || hor.sz){
ll xx;
if(ver.sz && hor.sz)xx=max(ver.bc.fr,hor.bc.fr);
else if(ver.sz) xx=ver.bc.fr;
else xx=hor.bc.fr;
while(hor.sz && hor.bc.fr==xx){
ll a=hor.bc.sc.fr,b=hor.bc.sc.sc;
hor.pop_back();
if(anc(a)!=anc(b)){
if(vis[{x[a]+1,y[a]-1}]==0){
vis[{x[a]+1,y[a]-1}]=1;
uni(a,b);
U.pb(a);
V.pb(b);
A.pb(x[a]+1);
B.pb(y[a]-1);
}
else if(vis[{x[a]+1,y[a]+1}]==0){
vis[{x[a]+1,y[a]+1}]=1;
uni(a,b);
U.pb(a);
V.pb(b);
A.pb(x[a]+1);
B.pb(y[a]+1);
}
}
}
while(ver.sz && ver.bc.fr==xx){
ll a=ver.bc.sc.fr,b=ver.bc.sc.sc;
ver.pop_back();
if(anc(a)!=anc(b)){
if(vis[{x[a]+1,y[a]+1}]==0){
vis[{x[a]+1,y[a]+1}]=1;
uni(a,b);
U.pb(a);
V.pb(b);
A.pb(x[a]+1);
B.pb(y[a]+1);
}
else if(vis[{x[a]-1,y[a]+1}]==0){
vis[{x[a]-1,y[a]+1}]=1;
uni(a,b);
U.pb(a);
V.pb(b);
A.pb(x[a]-1);
B.pb(y[a]+1);
}
}
}
}
if((int)V.size()!=n-1)return 0;
//~ for(int i=0;i<(int)V.size();i++)cout<<V[i]<<' '<<V[i]<<endl;
//~ for(auto i : A)cout<<i<<' ';
//~ cout<<endl;
//~ for(auto i : B)cout<<i<<' ';
//~ cout<<endl;
build(U,V,A,B);
return 1;
}
