#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define all(x) (x).begin(), (x).end()
struct dsu {
vector<int> p, sz;
dsu(int n) {
p.assign(n, 0);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
return (x == p[x] ? x : p[x] = find(p[x]));
}
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
return true;
}
};
int construct_roads(vector<int> x, vector<int> y) {
int n = (int)x.size();
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int, int>, int> id;
for (int i = 0; i < n; i++) id[MP(x[i], y[i])] = i;
vector<int> U, V, A, B;
vector<int> perm(n);
iota(all(perm), 0);
sort(all(perm), [&](int i, int j){
return MP(x[i], y[i]) < MP(x[j], y[j]);
});
dsu d(n);
for (int i : perm){
if (id.find(MP(x[i], y[i] + 2)) == id.end()) continue;
int j = id[MP(x[i], y[i] + 2)];
if (d.unite(i, j)){
U.push_back(i);
V.push_back(j);
}
}
for (int i : perm) {
if (id.find(MP(x[i] + 2, y[i])) == id.end()) continue;
int j = id[MP(x[i] + 2, y[i])];
if (d.unite(i, j)) {
U.push_back(i);
V.push_back(j);
}
}
if (U.size() != n - 1) return 0;
A.resize(n - 1);
B.resize(n - 1);
set<pair<int, int>> benches;
int k = 0;
for (int it = 0; it < n - 1; it++){
int i = U[it], j = V[it];
if (x[i] == x[j]){
B[it] = (y[i] + y[j]) / 2;
if (x[i] == 2 || x[i] == 6){
A[it] = (x[i] == 2 ? 1 : 7);
} else {
if (k){
A[it] = x[i] - 1;
} else {
A[it] = x[i] + 1;
}
k ^= 1;
}
benches.insert(MP(A[it], B[it]));
}
}
for (int it = 0; it < n - 1; it++) {
int i = U[it], j = V[it];
if (y[i] == y[j]) {
int xx = (x[i] + x[j]) / 2;
A[it] = xx;
if (!benches.count(MP(xx, y[i] + 1))){
B[it] = y[i] + 1;
} else
if (!benches.count(MP(xx, y[i] - 1))){
B[it] = y[i] - 1;
} else {
assert(false);
}
benches.insert(MP(A[it], B[it]));
}
}
build(U, V, A, B);
return 1;
}
