#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;
}
vector<pair<int,int>>eds;
for(int i=0; i<n; ++i) {
for(int j=0; j<4; ++j) {
int nx = x[i] + dx[j], ny = y[i] + dy[j];
if(ft.count(make_pair(nx, ny))) {
int she = ft[{nx, ny}];
if(find(i) == find(she)) continue;
g[i].push_back(she);
g[she].push_back(i);
unite(i, she);
eds.emplace_back(i, she);
}
}
}
trav(0);
for(int i=0; i<n; ++i) if(!vis[i]) {
return 0;
}
for(int i=0; i<n-1; ++i) {
auto [me, she] = eds[i];
int x0 = x[me], y0 = y[me], x1 = x[she], y1 = y[she];
if(x0 > x1) swap(eds[i].first, eds[i].second);
}
sort(eds.begin(), eds.end(), [&] (auto p, auto q) {
if(x[p.first]==x[q.first]) {
return max(y[p.first], y[p.second]) > max(y[q.first], y[q.second]);
}
return x[p.first] < x[q.first];
});
for(auto [me, she] : eds) {
u.push_back(me);
v.push_back(she);
int x0 = x[me], y0 = y[me], x1 = x[she], y1 = y[she];
if(x0==x1) { //vertical
if(!ben.count(make_pair(x0-1, y0 + y1 >> 1))) {
ben[{x0-1, y0 + y1 >> 1}] = 1;
a.push_back(x0-1);
b.push_back(y0 + y1 >> 1);
} else {
if(ben.count(make_pair(x0+1, y0 + y1 >> 1))) return 0;
ben[{x0+1, y0 + y1 >> 1}] = 1;
a.push_back(x0+1);
b.push_back(y0 + y1 >> 1);
}
} else {
if(!ben.count(make_pair(x0 + x1 >> 1, y0 + 1))) {
ben[{x0 + x1 >> 1, y0 + 1}] = 1;
a.push_back(x0 + x1 >> 1);
b.push_back(y0 + 1);
} else {
if(ben.count(make_pair(x0 + x1 >> 1, y0 - 1))) return 0;
ben[{x0 + x1 >> 1, y0 - 1}] = 1;
a.push_back(x0 + x1 >> 1);
b.push_back(y0 - 1);
}
}
}
build(u, v, a, b);
return 1;
}
