#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back
#define SZ(v) (int)v.size()
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define F first
#define S second
const int MX = 200005;
int n;
pii a[MX];
set<pair<pii,int> > st;
vector<pii> dir = {{-2,0},{2,0},{0,-2},{0,2}};
vi adj[MX];
int par[MX];
int find(int x){
if(par[x] == x) return x;
return par[x] = find(par[x]);
}
signed construct_roads(vector<signed> x, vector<signed> y){
n = SZ(x);
REP(i,n){
a[i] = {x[i],y[i]};
st.insert({a[i],i});
par[i] = i;
}
vector<pii> edges;
REP(i,n){
REP(j,4){
pii bruh = {x[i]+dir[j].F,y[i]+dir[j].S};
auto it = st.lower_bound({bruh,0});
if(it != st.end()){
if((*it).F == bruh){
adj[i].pb((*it).S);
if(i < (*it).S) edges.pb({i,(*it).S});
}
}
}
}
vector<signed> u0, v0, a0, b0;
for(auto i:edges){
int u = i.F,v = i.S;
// cout << u << " " << v << "\n";
if(find(u) == find(v)) continue;
if(a[u] > a[v]) swap(u,v);
if(x[u] != x[v]){
continue;
}
else{
par[find(u)] = find(v);
u0.pb(u);
v0.pb(v);
if(x[u] == 2){
a0.pb(x[u]-1);
b0.pb(y[u]+1);
}
else if(x[u] == 6){
a0.pb(x[u]+1);
b0.pb(y[u]+1);
}
else if((x[u]+y[u])%4 == 0){
a0.pb(x[u]-1);
b0.pb(y[u]+1);
}
else{
a0.pb(x[u]+1);
b0.pb(y[u]+1);
}
}
}
for(auto i:edges){
int u = i.F,v = i.S;
// cout << u << " " << v << "\n";
if(find(u) == find(v)) continue;
if(a[u] > a[v]) swap(u,v);
if(x[u] != x[v]){
par[find(u)] = find(v);
u0.pb(u);
v0.pb(v);
if((x[u]+y[u])%4 == 0){
a0.pb(x[u]+1);
b0.pb(y[u]+1);
}
else{
a0.pb(x[u]+1);
b0.pb(y[u]-1);
}
}
else{
continue;
}
}
REP(i,n){
if(find(i) != find(1)) return 0;
}
build(u0, v0, a0, b0);
return 1;
}
