#include "parks.h"
#include <bits/stdc++.h>
using std::array;
using std::pair;
using std::tuple;
using std::vector;
using ll = long long;
template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;
template <class F>
struct fixed : private F {
explicit fixed(F&& f) : F(std::forward<F>(f)) {}
template <class... Args>
decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
struct UnionFind {
vector<int> data;
explicit UnionFind(const int n) : data(n, -1) {}
int find(const int u) {
return data[u] < 0 ? u : data[u] = find(data[u]);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (data[x] > data[y]) std::swap(x, y);
data[x] += data[y];
data[y] = x;
return true;
}
};
int construct_roads(vector<int> X, vector<int> Y) {
const int N = (int)X.size();
std::map<pair<int, int>, int> map;
for (int i = 0; i < N; ++i) {
map[{X[i], Y[i]}] = i;
}
UnionFind dsu(N);
vector<array<int, 4>> edges;
vector<int> up(N, -1), left(N, -1), right(N, -1);
for (const auto& [p, i] : map) {
const auto& [x, y] = p;
const auto itr = map.find(pair(x, y + 2));
if (itr != map.end()) {
const int j = itr->second;
if (!dsu.merge(i, j)) {
continue;
}
if (x == 2) {
edges.push_back({i, j, x - 1, y + 1});
} else if (x == 6) {
edges.push_back({i, j, x + 1, y + 1});
} else {
up[i] = (int)edges.size();
edges.push_back({i, j, -1, -1});
}
}
}
for (const auto& [p, i] : map) {
const auto& [x, y] = p;
const auto itr = map.find(pair(x + 2, y));
if (itr != map.end()) {
const int j = itr->second;
if (!dsu.merge(i, j)) {
continue;
}
if (x == 2) {
left[j] = (int)edges.size();
edges.push_back({i, j, -1, -1});
} else {
right[i] = (int)edges.size();
edges.push_back({i, j, -1, -1});
}
}
}
if ((int)edges.size() != N - 1) {
return 0;
}
std::set<pair<int, int>> used;
for (const auto& [p, i] : map) {
if (X[i] != 4) {
continue;
}
if (left[i] != -1) {
const int x = 3;
const int y = used.find(pair(x, Y[i] - 1)) != used.end() ? Y[i] + 1 : Y[i] - 1;
used.emplace(x, y);
edges[left[i]][2] = x;
edges[left[i]][3] = y;
}
if (right[i] != -1) {
const int x = 5;
const int y = used.find(pair(x, Y[i] - 1)) != used.end() ? Y[i] + 1 : Y[i] - 1;
used.emplace(x, y);
edges[right[i]][2] = x;
edges[right[i]][3] = y;
}
if (up[i] != -1) {
const int y = Y[i] + 1;
const int x = used.find(pair(3, y)) != used.end() ? 5 : 3;
used.emplace(x, y);
edges[up[i]][2] = x;
edges[up[i]][3] = y;
}
}
vector<int> U, V, A, B;
for (const auto& [u, v, a, b] : edges) {
U.push_back(u);
V.push_back(v);
A.push_back(a);
B.push_back(b);
}
build(U, V, A, B);
return 1;
}
