#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
#define ll int
#define ins insert
#define sz size()
#define vll vector<ll>
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
using namespace std;
const int N=2e5+5;
const int inf=1e9;
map<pair<ll,ll>, ll> f;
vll xx, yy;
ll xd[4] = {2, 0}, yd[4] = {0, 2};
ll bx[2][4] = {{1, -1}, { 1, 1}};
ll by[2][4] = {{1, 1}, {-1, 1}};
set<pair<ll,ll>> vis;
vll v,u,a,b;
ll n,c;
ll p[N], siz[N];
bool ok(ll x,ll y){
if(x % 2) return (vis.find({x, y}) == vis.end());
return f[{x,y}];
}
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;
}
void go(ll x, ll y){
c++;
for(ll i=0;i<2;i++){
ll nx = x + xd[i], ny = y + yd[i];
ll p = (x + y) / 2 % 2;
ll aa = x + bx[p][i], bb = y + by[p][i];
if(!ok(nx, ny) || !ok(aa, bb) || !uni(f[{nx,ny}],f[{x,y}])) continue;
v.pb(f[{x,y}]-1);
u.pb(f[{nx,ny}]-1);
a.pb(aa);
b.pb(bb);
vis.ins({aa, bb});
}
}
int construct_roads(vector<int> X, vector<int> Y) {
n=X.size();
vector<array<int,3>> V;
for(int i=0;i<n;i++){
f[{X[i], Y[i]}] = i + 1;
V.pb({X[i] + Y[i], X[i], i + 1});
}
sort(all(V));
xx.pb(0);
yy.pb(0);
for(auto i : X) xx.pb(i);
for(auto i : Y) yy.pb(i);
for(ll i=1;i<=n;i++){p[i]=i,siz[i]=1;}
for(ll i=0;i<n;i++){
ll x = xx[V[i][2]];
ll y = yy[V[i][2]];
//~ cout<<x<<' '<<y<<endl;
go(x,y);
}
//~ for(ll i=0;i<(ll)u.size();i++){
//~ cout<<X[v[i]]<<' '<<Y[v[i]]<<endl;
//~ cout<<X[u[i]]<<' '<<Y[u[i]]<<endl;
//~ cout<<a[i]<<' '<<b[i]<<endl;
//~ cout<<endl;
//~ }
if((ll)u.size() != n - 1) return 0;
build(u, v, a, b);
return 1;
}
