#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
const int nax = 200000;
vector<int>g[nax];
bool vis[nax];
int par[nax], sz[nax];
void trav(int v) {
vis[v] = 1;
for(int u : g[v]) if(!vis[u]) {
trav(u);
}
}
int find(int v) {
return par[v] = (v==par[v]) ? v : find(par[v]);
}
void unite(int u, int v) {
u = find(u), v = find(v);
if(sz[u] < sz[v]) swap(u, v);
sz[u] += sz[v];
par[v] = u;
}
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
map<pair<int,int>, int>ft;
for(int i=0; i<n; ++i) {
ft[{x[i], y[i]}] = i;
}
int dx[] = {2, -2, 0, 0};
int dy[] = {0, 0, 2, -2};
vector<int>u, v, a, b;
map<pair<int,int>, int>ben;
for(int i=0; i<n; ++i) {
par[i] = i, sz[i] = 1;
}
for(int i=0; i<n; ++i) {
for(int j=2; j<4; ++j) {
int nx = x[i] + dx[j], ny = y[i] + dy[j];
if(ft.count(make_pair(nx, ny))) {
if(find(i) == find(ft[{nx, ny}])) continue;
if((y[i]+ny)%8<4) {
a.push_back(x[i]-1);
b.push_back(y[i] + ny >> 1);
ben[{x[i]-1, y[i] + ny >> 1}] = 1;
} else {
a.push_back(x[i]+1);
b.push_back(y[i] + ny >> 1);
ben[{x[i]+1, y[i] + ny >> 1}] = 1;
}
g[i].push_back(ft[{nx, ny}]);
g[ft[{nx, ny}]].push_back(i);
unite(i, ft[{nx, ny}]);
u.push_back(i);
v.push_back(ft[{nx, ny}]);
}
}
}
for(int i=0; i<n; ++i) {
if(ft.count(make_pair(x[i]+dx[0], y[i]))
+ ft.count(make_pair(x[i]+dx[1], y[i]))==1) {
for(int j=0; j<2; ++j) {
int nx = x[i] + dx[j], ny = y[i] + dy[j];
if(!ft.count(make_pair(nx, ny))) continue;
int she = ft[{nx, ny}];
if(find(i) == find(she)) continue;
g[i].push_back(she);
g[she].push_back(i);
unite(i, she);
u.push_back(i);
v.push_back(she);
if(!ben.count(make_pair(x[i] + nx >> 1, ny - 1))) {
ben[{x[i] + nx >> 1, ny - 1}] = 1;
a.push_back(x[i] + nx >> 1);
b.push_back(ny - 1);
} else if(!ben.count(make_pair(x[i] + nx >> 1, ny + 1))) {
ben[{x[i] + nx >> 1, ny + 1}] = 1;
a.push_back(x[i] + nx >> 1);
b.push_back(ny + 1);
} else return 0;
}
}
}
trav(0);
for(int i=0; i<n; ++i) if(!vis[i]) {
return 0;
}
build(u, v, a, b);
return 1;
}
