#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
struct DSU {
vector<int> P, S;
DSU(int n) {
P.resize(n+1);
S.resize(n+1, 1);
for (int i = 1; i <= n; i++) P[i] = i;
}
int find(int x) {
if (x == P[x]) return x;
return P[x] = find(P[x]);
}
bool merge(int a, int b) {
a = find(a); b = find(b);
if (a == b) return 0;
if (S[a] < S[b]) swap(a, b);
S[a] += S[b];
P[b] = a;
return 1;
}
int same(int a, int b) {
return find(a) == find(b);
}
};
vector<int> dx = {-2, 2, 0, 0};
vector<int> dy = {0, 0, 2, -2};
bool ok(vector<int> X, vector<int> Y, vector<pair<int, int>> edges, vector<int> &u, vector<int> &v, vector<int> &a, vector<int> &b, int pr) {
set<pair<int, int>> st;
for (auto [i, j]: edges) {
if (X[i] == X[j]) {
// vertical
int x = X[i] - 1;
int y = (Y[i] + Y[j])/2;
if ((x/2 + y/2) % 2 == pr) {
x = X[i] + 1;
}
if (st.find({x, y}) != st.end()) {
u.clear(); v.clear(); a.clear(); b.clear();
return 0;
}
u.push_back(i);
v.push_back(j);
a.push_back(x);
b.push_back(y);
st.insert({x, y});
} else {
// horizontal
int x = (X[i] + X[j])/2;
int y = Y[i]-1;
if ((x/2 + y/2) % 2 != pr) {
y = Y[i] + 1;
}
if (st.find({x, y}) != st.end()) {
u.clear(); v.clear(); a.clear(); b.clear();
return 0;
}
u.push_back(i);
v.push_back(j);
a.push_back(x);
b.push_back(y);
st.insert({x, y});
}
}
return 1;
}
int construct_roads(vector<int> X, vector<int> Y) {
int n = X.size();
map<pair<int, int>, int> id;
for (int i = 0; i < n; i++) {
id[{X[i], Y[i]}] = i;
}
DSU d(n);
int cc = n;
vector<pair<int, int>> edges;
for (int i = 0; i < n; i++) {
if ((X[i]/2 + Y[i]/2) % 2) continue;
for (int j = 0; j < 4; j++) {
int x = X[i] + dx[j];
int y = Y[i] + dy[j];
if (id.find({x, y}) != id.end()) {
int u = id[{x, y}];
if (!d.same(i, u)) {
edges.emplace_back(i, u);
d.merge(i, u);
cc--;
}
}
}
}
if (cc != 1) return 0;
vector<int> u, v, a, b;
if (ok(X, Y, edges, u, v, a, b, 0)) {
build(u, v, a, b);
return 1;
}
if (ok(X, Y, edges, u, v, a, b, 1)) {
build(u, v, a, b);
return 1;
}
return 1;
}
