#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> e;
DSU (int n) {
e = vector<int>(n, -1);
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
vector<array<int, 3>> st;
int N = x.size();
for (int i = 0; i < N; ++i) {
st.push_back({y[i], x[i], i});
}
sort(begin(st), end(st));
vector<array<int, 2>> con;
for (int i = 1; i < N; ++i) {
if (st[i][0] == st[i - 1][0] && st[i][1] - st[i - 1][1] == 2) {
con.push_back({st[i][2], st[i - 1][2]});
}
}
DSU dsu(N);
for (auto& [i, j] : con) {
dsu.unite(i, j);
}
st.clear();
for (int i = 0; i < N; ++i) {
st.push_back({x[i], y[i], i});
}
sort(begin(st), end(st));
vector<array<int, 2>> ncon;
for (int i = 1; i < N; ++i) {
if (st[i][0] == st[i - 1][0] && st[i][1] - st[i - 1][1] == 2) {
ncon.push_back({st[i][2], st[i - 1][2]});
}
}
sort(begin(ncon), end(ncon), [&](array<int, 2> a, array<int, 2> b) {
int nx = x[a[0]];
int nx1 = x[b[0]];
if (nx == 2 || nx == 6) return true;
if (nx1 == 2 || nx1 == 6) return false;
return nx < nx1;
});
vector<bool> keep(ncon.size());
for (int it = 0; it < ncon.size(); ++it) {
int i = ncon[it][0];
int j = ncon[it][1];
keep[it] = dsu.unite(i, j);
}
vector<array<int, 2>> tmp;
for (int it = 0; it < ncon.size(); ++it) {
if (keep[it]) tmp.push_back(ncon[it]);
}
ncon = tmp;
for (auto& [i, j] : ncon) {
con.push_back({i, j});
}
if (-dsu.e[dsu.get(0)] != N) return 0;
vector<int> v, u, a, b;
set<array<int, 2>> vis;
for (auto& [i, j] : con) {
if (y[i] == y[j]) {
int nx = min(x[i], x[j]) + 1;
int ny;
if (nx == 3) {
ny = y[i] - 1;
} else {
assert(nx == 5);
ny = y[i] + 1;
}
vis.insert({nx, ny});
v.push_back(i);
u.push_back(j);
a.push_back(nx);
b.push_back(ny);
} else {
int nx, ny;
assert(x[i] == x[j]);
ny = min(y[i], y[j]) + 1;
if (x[i] == 2) {
nx = x[i] - 1;
} else if (x[i] == 6) {
nx = x[i] + 1;
} else {
assert(x[i] == 4);
nx = x[i] - 1;
if (vis.count({nx, ny})) {
nx = x[i] + 1;
}
}
assert(!vis.count({nx, ny}));
vis.insert({nx, ny});
v.push_back(i);
u.push_back(j);
a.push_back(nx);
b.push_back(ny);
}
}
build(u, v, a, b);
return 1;
}
