#include "parks.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second
struct dsu {
vector<int> p, size;
void init(int n) {
p.assign(n, 0); size.assign(n, 1);
for (int i = 0; i < n; i++) p[i] = i;
}
int get(int a) {
return p[a] == a ? a : p[a] = get(p[a]);
}
void merge(int a, int b) {
a = get(a); b = get(b);
if (a == b) return;
if (size[a] > size[b]) swap(a, b);
size[b] += size[a];
p[a] = b;
}
};
int construct_roads(std::vector<int> X, std::vector<int> Y) {
int n = X.size();
vector<array<int, 3>> a(n);
vector<pair<int, int>> all;
for (int i = 0; i < n; i++) {
a[i] = array<int, 3>{X[i], Y[i], i};
all.emplace_back(X[i] - 1, Y[i] - 1);
all.emplace_back(X[i] - 1, Y[i] + 1);
all.emplace_back(X[i] + 1, Y[i] - 1);
all.emplace_back(X[i] + 1, Y[i] + 1);
}
sort(a.begin(), a.end());
sort(all.begin(), all.end());
all.resize(unique(all.begin(), all.end()) - all.begin());
auto id = [&](int x, int y) -> int {
int i = lower_bound(a.begin(), a.end(), array<int, 3>{x, y, 0}) - a.begin();
if (i == n) return -1;
return a[i][0] == x and a[i][1] == y ? a[i][2] : -1;
};
dsu ds; ds.init(n);
vector<tuple<int, int, int, int>> ans;
for (auto [x, y]: all) {
for (int t = 0; t < 2; t++) {
if ((x + y) % 4 == t * 2) {
int i = id(x - 1, y - 1), j = id(x - 1, y + 1);
if (min(i, j) >= 0 and ds.get(i) != ds.get(j)) {
ds.merge(i, j);
ans.emplace_back(x, y, i, j);
break;
}
i = id(x + 1, y - 1), j = id(x + 1, y + 1);
if (min(i, j) >= 0 and ds.get(i) != ds.get(j)) {
ds.merge(i, j);
ans.emplace_back(x, y, i, j);
break;
}
} else {
int i = id(x - 1, y - 1), j = id(x + 1, y - 1);
if (min(i, j) >= 0 and ds.get(i) != ds.get(j)) {
ds.merge(i, j);
ans.emplace_back(x, y, i, j);
break;
}
i = id(x - 1, y + 1), j = id(x + 1, y + 1);
if (min(i, j) >= 0 and ds.get(i) != ds.get(j)) {
ds.merge(i, j);
ans.emplace_back(x, y, i, j);
break;
}
}
}
}
bool ok = true;
for (int i = 1; i < n; i++) ok &= ds.get(i) == ds.get(0);
if (!ok) return 0;
vector<int> U, V, A, B;
for (auto [a, b, u, v]: ans) {
U.emplace_back(u);
V.emplace_back(v);
A.emplace_back(a);
B.emplace_back(b);
}
build(U, V, A, B);
return 1;
}
