#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
struct DisjointSet {
int n;
vector<int> parent, rank;
DisjointSet(int _n) : n(_n) {
parent.resize(n);
iota(parent.begin(), parent.end(), 0);
rank.resize(n, 0);
}
int find(int u) {
return parent[u] = (u == parent[u] ? u : find(parent[u]));
}
void merge(int u, int v) {
u = find(u); v = find(v);
if (u == v) return;
if (rank[u] > rank[v]) swap(u, v);
parent[u] = v;
if (rank[u] == rank[v]) ++rank[v];
}
};
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
vector<int> p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int a, int b) {
return pii{x[a],y[a]} < pii{x[b], y[b]};
});
DisjointSet dsu(n);
map<pii, int> fountains;
vector<vector<pii>> points(200001);
int min_x = 200000;
set<pii> benches;
vector<int> u, v, a, b;
for (int i=0; i<n; ++i) fountains[{ x[i], y[i] }] = i, min_x = min(min_x, x[i]);
for (int i=0; i<n; ++i) points[x[i]].push_back({ y[i], i });
for (int i=0; i<points.size(); i+=2) sort(points[i].begin(), points[i].end());
for (int j=0; j+1<points[min_x].size(); ++j) {
if (points[min_x][j].first + 2 == points[min_x][j+1].first) {
dsu.merge(points[min_x][j].second, points[min_x][j+1].second);
u.push_back(points[min_x][j].second);
v.push_back(points[min_x][j+1].second);
a.push_back(min_x-1);
b.push_back(points[min_x][j].first + 1);
benches.insert({ points[min_x][j].first + 1, min_x-1 });
}
}
for (int x=min_x+2; x<points.size(); x+=2) {
for (int j=0; j<points[x].size(); ++j) {
auto[y1, i1] = points[x][j];
if (fountains.find({ x-2, y1 }) != fountains.end()) {
int idx = fountains[{x-2, y1}];
if (dsu.find(idx) != dsu.find(i1)) {
dsu.merge(idx, i1);
u.push_back(idx);
v.push_back(i1);
a.push_back(x-1);
if (benches.find({x-1, y1-1}) != benches.end()) {
assert(benches.find({x-1, y1+1}) == benches.end());
b.push_back(y1+1);
} else {
b.push_back(y1-1);
}
benches.insert({ a.back(), b.back() });
}
}
if (j+1 == points[x].size()) break;
auto[y2, i2] = points[x][j+1];
if (y1 + 2 == y2) {
dsu.merge(i1, i2);
u.push_back(i1);
v.push_back(i2);
b.push_back(y1+1);
if (benches.find({x-1, y1+1}) != benches.end()) {
assert(benches.find({x+1, y1+1}) == benches.end());
a.push_back(x+1);
} else {
a.push_back(x-1);
}
benches.insert({ a.back(), b.back() });
}
}
}
for (int i=1; i<n; ++i) {
if (dsu.find(i) != dsu.find(0)) {
return 0;
}
}
build(u, v, a, b);
return 1;
}
