#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
int dx[4] = {2,-2,0,0};
int dy[4] = {0,0,2,-2};
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
const int mxN = (int)2e5 + 5;
vector<int>parent(mxN);
int UF(int u) {
if(parent[u] == u) return u;
return parent[u] = UF(parent[u]);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
const int n = (int)x.size();
for(int i = 0 ; i < n ; i++)
parent[i] = i;
set<pair<int,int>>s;
map<pair<int,int>,int>mp;
for(int i = 0 ; i < n ; i++)
mp[{x[i],y[i]}] = i;
vector<int>u(n-1),v(n-1),a(n-1),b(n-1);
map<pair<int,int>,bool>processed;
for(int i = 0 ; i < n ; i++) {
for(int d = 0 ; d < 4 ; d++) {
processed[{x[i],y[i]}] = 1;
if(mp.count({x[i] + dx[d], y[i] + dy[d]})) {
if(processed[{x[i] + dx[d], y[i] + dy[d]}])
continue;
int f = mp[{x[i] + dx[d], y[i] + dy[d]}];
if(dx[d] == 0) {
if(s.count({x[i]+1,y[i] + dy[d]/2}))
a[i] = x[i]-1, b[i] = y[i] + dy[d]/2, u[i] = i, v[i] = f, s.insert({a[i],b[i]}), parent[UF(i)] = UF(f);
else
a[i] = x[i]+1, b[i] = y[i] + dy[d]/2, u[i] = i, v[i] = f, s.insert({a[i],b[i]}), parent[UF(i)] = UF(f);
} else {
if(s.count({x[i] + dx[d]/2, y[i]+1}))
a[i] = x[i] + dx[d]/2, b[i] = y[i]-1, u[i] = i, v[i] = f, s.insert({a[i],b[i]}), parent[UF(i)] = UF(f);
else
a[i] = x[i] + dx[d]/2, b[i] = y[i]+1, u[i] = i, v[i] = f, s.insert({a[i],b[i]}), parent[UF(i)] = UF(f);
}
}
}
}
int cnt = 0;
for(int i = 0 ; i < n ; i++)
cnt += parent[i] == i;
for(int i = 0 ; i < n-1 ; i++) {
if(a[i] == 0 && b[i] == 0)
return 0;
}
if(cnt > 1)
return 0;
build(u,v,a,b);
return 1;
}
