#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7;
int F[LIM], n, dx[]={1, 0, -1, 0}, dy[]={0, 1, 0, -1};
map<pair<int,int>,int>mp, odw;
int fnd(int x) {
if(F[x]==x) return x;
return F[x]=fnd(F[x]);
}
bool uni(int a, int b) {
if(fnd(a)==fnd(b)) return false;
F[fnd(b)]=fnd(a);
return true;
}
int construct_roads(vector<int>x, vector<int>y) {
n=x.size();
rep(i, n) mp[{x[i], y[i]}]=i;
rep(i, n) F[i]=i;
vector<pair<int,pair<int,int>>>V;
vector<int>u, v, a, b;
rep(i, n) if(mp.find({x[i], y[i]+2})!=mp.end()) V.pb({x[i], {i, mp[{x[i], y[i]+2}]}});
sort(all(V));
for(auto i : V) {
pair<int,int>p={x[i.nd.st], y[i.nd.st]+1};
if(abs((p.st+p.nd+1)/2)%2==0) ++p.st; else --p.st;
if(odw[p]) continue;
if(uni(i.nd.st, i.nd.nd)) {
u.pb(i.nd.st);
v.pb(i.nd.nd);
a.pb(p.st);
b.pb(p.nd);
odw[p]=1;
}
}
V.clear();
rep(i, n) if(mp.find({x[i]+2, y[i]})!=mp.end()) V.pb({y[i], {i, mp[{x[i]+2, y[i]}]}});
sort(all(V));
for(auto i : V) {
pair<int,int>p={x[i.nd.st]+1, y[i.nd.st]};
if(abs((p.st+p.nd+1)/2)%2==1) ++p.nd; else --p.nd;
if(odw[p]) continue;
if(uni(i.nd.st, i.nd.nd)) {
u.pb(i.nd.st);
v.pb(i.nd.nd);
a.pb(p.st);
b.pb(p.nd);
odw[p]=1;
}
}
rep(i, n) if(fnd(i)!=fnd(0)) return 0;
build(u, v, a, b);
return 1;
}
