#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<<'\n';
#define vvi vector<vi>
#define vb vector<bool>
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));
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;
}
vi u,v,a,b;
map<pii,vi>fight;
map<pii,int>fc;
f0r(i,n){
for(auto s : adj(mp(x[i], y[i]))){
if(m.count(s) && m[s] > i){
u.pb(i); v.pb(m[s]);
unite(i, m[s]);
int x1 = x[i]; int y1 = y[i]; int x2 = x[m[s]]; int y2 = y[m[s]];
if(x1 == x2){
fight[mp(x1 + 1, (y1 + y2) / 2)].pb(u.size() - 1);
fight[mp(x1 - 1, (y1 + y2) / 2)].pb(u.size() - 1);
}
else{
fight[mp((x1 + x2) / 2, y1 + 1)].pb(u.size() - 1);
fight[mp((x1 + x2) / 2, y1 - 1)].pb(u.size() - 1);
}
}
}
}
if(ccs > 1)return 0;
queue<pii>q; //stores benches
for(auto u : fight){
fc[u.first] = u.second.size();
if(u.second.size() == 1){
q.push(u.first);
}
}
if(q.empty()){
for(auto u : fight){
if(u.second.size() == 2){
q.push(u.first);
break;
}
}
}
vb vis(u.size());
a.resize(u.size()); b.resize(u.size());
while(!q.empty()){
pii node = q.front(); q.pop();
fc[node] = 0;
// cout<<node.first<<' '<<node.second<<'\n';
for(auto cur : fight[node]){
if(!vis[cur]){
a[cur] = node.first; b[cur] = node.second; vis[cur] = 1;
int x1 = x[u[cur]]; int x2 = x[v[cur]]; int y1 = y[u[cur]]; int y2 = y[v[cur]];
if(x1 == x2){
if(fc.count(mp(x1 + 1, (y1 + y2) / 2))){
fc[mp(x1 + 1, (y1 + y2) / 2)]--;
if(fc[mp(x1 + 1, (y1 + y2) / 2)] == 1){
q.push(mp(x1 + 1, (y1 + y2) / 2));
}
}
if(fc.count(mp(x1 - 1, (y1 + y2) / 2))){
fc[mp(x1 - 1, (y1 + y2) / 2)]--;
if(fc[mp(x1 - 1, (y1 + y2) / 2)] == 1){
q.push(mp(x1 - 1, (y1 + y2) / 2));
}
}
}
else{
if(fc.count(mp((x1 + x2) / 2, y1 + 1))){
fc[mp((x1 + x2) / 2, y1 + 1)]--;
if(fc[mp((x1 + x2) / 2, y1 + 1)] == 1){
q.push(mp((x1 + x2) / 2, y1 + 1));
}
}
if(fc.count(mp((x1 + x2) / 2, y1 - 1))){
fc[mp((x1 + x2) / 2, y1 - 1)]--;
if(fc[mp((x1 + x2) / 2, y1 - 1)] == 1){
q.push(mp((x1 + x2) / 2, y1 - 1));
}
}
}
break;
}
}
}
/*
bool ok = 1;
f0r(i, u.size()){
if(!vis[i])ok= 0;
}
if(!ok)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;
*/
}
