#include "parks.h"
#include <set>
#include <map>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
int uf[200006];
int _find(int x) {
if (uf[x] == -1) return x;
return uf[x] = _find(uf[x]);
}
bool _merge(int x, int y) {
x = _find(x), y = _find(y);
if (x != y) return uf[x] = y, true;
return false;
}
set<pair<int, int>> points;
map<pair<int, int>, int> fountains;
vector<pair<int, int>> edges, sel;
int construct_roads(vector<int> x, vector<int> y) {
int n = (int)x.size();
for (int i = 0; i < n; i++) uf[i] = -1;
for (int i = 0; i < n; i++) {
points.insert({ x[i] - 1, y[i] - 1 });
points.insert({ x[i] - 1, y[i] + 1 });
points.insert({ x[i] + 1, y[i] - 1 });
points.insert({ x[i] + 1, y[i] + 1 });
fountains[{ x[i], y[i] }] = i;
}
for (auto &i: points) {
if ((i.first / 2 + i.second / 2) % 2) {
bool pos = false;
if (!pos && fountains.find({ i.first - 1, i.second - 1 }) != fountains.end() && fountains.find({ i.first + 1, i.second - 1 }) != fountains.end()) {
int a = fountains[{ i.first - 1, i.second - 1 }], b = fountains[{ i.first + 1, i.second - 1 }];
if (_merge(a, b)) {
edges.push_back({ a, b });
sel.push_back(i);
pos = true;
}
}
if (!pos && fountains.find({ i.first - 1, i.second + 1 }) != fountains.end() && fountains.find({ i.first + 1, i.second + 1 }) != fountains.end()) {
int a = fountains[{ i.first - 1, i.second + 1 }], b = fountains[{ i.first + 1, i.second + 1 }];
if (_merge(a, b)) {
edges.push_back({ a, b });
sel.push_back(i);
pos = true;
}
}
} else {
bool pos = false;
if (!pos && fountains.find({ i.first - 1, i.second - 1 }) != fountains.end() && fountains.find({ i.first - 1, i.second + 1 }) != fountains.end()) {
int a = fountains[{ i.first - 1, i.second - 1 }], b = fountains[{ i.first - 1, i.second + 1 }];
if (_merge(a, b)) {
edges.push_back({ a, b });
sel.push_back(i);
pos = true;
}
}
if (!pos && fountains.find({ i.first + 1, i.second - 1 }) != fountains.end() && fountains.find({ i.first + 1, i.second + 1 }) != fountains.end()) {
int a = fountains[{ i.first + 1, i.second - 1 }], b = fountains[{ i.first + 1, i.second + 1 }];
if (_merge(a, b)) {
edges.push_back({ a, b });
sel.push_back(i);
pos = true;
}
}
}
}
if ((int)edges.size() < n - 1) return 0;
vector<int> u(n - 1), v(n - 1), a(n - 1), b(n - 1);
for (int i = 0; i < n - 1; i++) u[i] = edges[i].first, v[i] = edges[i].second, a[i] = sel[i].first, b[i] = sel[i].second;
build(u, v, a, b);
return 1;
}
