#include "parks.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<endl;
#define vvi vector<vi>
#define vb vector<bool>
#define vpii vector<pair<int,int>>
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl;
using namespace std;
vector<pii> adj(pii x){
int a = x.first; int b = x.second;
return {mp(a+2, b), mp(a-2, b), mp(a, b+2), mp(a, b-2)};
}
const int mxn = 2e5 + 5;
vi sz(mxn), par(mxn);
int find(int x){
while(x != par[x])x = par[x];
return x;
}
int ccs;
void unite(int a, int b){
a = find(a); b = find(b);
if(a == b)return;
ccs--;
if(sz[a] < sz[b])swap(a,b);
sz[a] += sz[b];
par[b] = a;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
// vector<vector<int>>grid(2, vi(mxn, -1));
vi u,v,a,b;
int n = x.size();
map<pii,int>m;
ccs = n;
f0r(i,n){
m[mp(x[i], y[i])] = i;
par[i] = i;
sz[i] = 1;
}
vpii edges;
f0r(i,n){
for(auto u : adj(mp(x[i], y[i]))){
if(m.count(u) && m[u] > i){
edges.pb(mp(-(y[i] + u.second)/2, (x[i] + u.first)/2));
}
}
}
sort(edges.begin(), edges.end());
set<pii>benches;
f0r(i, edges.size()){
int x = edges[i].second; int y = -edges[i].first;
// cout<<x<<' '<<y<<'\n';
if(x % 2 == 0){
int u1 = m[mp(x, y-1)]; int u2 = m[mp(x, y+1)];
if(x % 4 == 0){
// dout2(x-1,y);
if(!benches.count(mp(x+1, y))){
benches.insert(mp(x+1, y));
u.pb(u1); v.pb(u2);
a.pb(x+1); b.pb(y);
}
}
else{
// dout2(x+1,y);
if(!benches.count(mp(x-1, y))){
benches.insert(mp(x-1, y));
u.pb(u1); v.pb(u2);
a.pb(x-1); b.pb(y);
}
}
}
else{
int u1 = m[mp(x-1, y)]; int u2 = m[mp(x+1, y)];
if(y % 4 == 0){
// dout2(x,y+1);
if(!benches.count(mp(x, y-1))){
benches.insert(mp(x,y-1));
u.pb(u1); v.pb(u2);
a.pb(x); b.pb(y-1);
}
}
else{
// dout2(x,y-1);
if(!benches.count(mp(x, y+1))){
benches.insert(mp(x, y+1));
u.pb(u1); v.pb(u2);
a.pb(x); b.pb(y+1);
}
}
}
}
f0r(i, u.size()){
// dout2(u[i], v[i]);
unite(u[i], v[i]);
}
if(ccs != 1)return 0;
build(u,v,a,b);
return 1;
/*
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
std::vector<int> u, v, a, b;
u.push_back(0);
v.push_back(1);
a.push_back(x[0]+1);
b.push_back(y[0]-1);
build(u, v, a, b);
return 1;
*/
}
