#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
struct DisjointSet{
vector<int> par;
void init(int n) {
par.resize(n);
iota(par.begin(), par.end(), 0);
}
int Find(int x) {
if (x == par[x]) return x;
return par[x] = Find(par[x]);
}
void Union(int x, int y) {
x = Find(x);
y = Find(y);
par[y] = x;
}
};
DisjointSet dsu;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int construct_roads(vector<int> x, vector<int> y) {
int N = x.size();
set<pair<int,int>> bench;
map<pair<int,int>,int> num;
for (int i=0; i<N; i++) {
num[{x[i], y[i]}] = i;
bench.insert({x[i]+1, y[i]+1});
bench.insert({x[i]+1, y[i]-1});
bench.insert({x[i]-1, y[i]+1});
bench.insert({x[i]-1, y[i]-1});
}
dsu.init(N);
set<pair<int,int>> ban;
vector<pair<int,int>> edge;
for (auto &[X, Y] : bench) {
if (num.find({X+1, Y+1}) == num.end()) continue;
if (num.find({X+1, Y-1}) == num.end()) continue;
if (num.find({X-1, Y+1}) == num.end()) continue;
if (num.find({X-1, Y-1}) == num.end()) continue;
int v1 = num[{X-1, Y-1}], v2 = num[{X-1, Y+1}], v3 = num[{X+1, Y+1}], v4 = num[{X+1, Y-1}];
if ((X + Y) % 4 == 0) {
if (dsu.Find(v2) != dsu.Find(v3)) {
dsu.Union(v2, v3);
edge.emplace_back(v2, v3);
}
if (dsu.Find(v3) != dsu.Find(v4)) {
dsu.Union(v3, v4);
edge.emplace_back(v3, v4);
}
ban.insert({v1, v4});
ban.insert({v4, v1});
}
else {
if (dsu.Find(v1) != dsu.Find(v2)) {
dsu.Union(v1, v2);
edge.emplace_back(v1, v2);
}
if (dsu.Find(v1) != dsu.Find(v4)) {
dsu.Union(v1, v4);
edge.emplace_back(v1, v4);
}
ban.insert({v3, v4});
ban.insert({v4, v3});
}
}
for (int i=0; i<N; i++) {
for (int k=0; k<4; k++) {
int nx = x[i] + dx[k] * 2;
int ny = y[i] + dy[k] * 2;
if (num.find({nx, ny}) == num.end()) continue;
if (dsu.Find(num[{nx, ny}]) != dsu.Find(i)) {
if (ban.find({num[{nx, ny}], i}) == ban.end()) {
dsu.Union(num[{nx, ny}], i);
edge.emplace_back(num[{nx, ny}], i);
}
}
}
}
int cnt = 0;
for (int i=0; i<N; i++) {
if (dsu.Find(i) == i) cnt ++;
}
if (cnt != 1) return 0;
vector<int> U, V, A, B;
for (auto &[u, v] : edge) {
U.push_back(u);
V.push_back(v);
if (x[u] == x[v]) {
B.push_back((y[u] + y[v]) / 2);
if ((x[u] + 1 + B.back()) % 4 == 2) A.push_back(x[u] + 1);
else A.push_back(x[u] - 1);
}
else {
A.push_back((x[u] + x[v]) / 2);
if ((y[u] + 1 + A.back()) % 4 == 0) B.push_back(y[u] + 1);
else B.push_back(y[u] - 1);
}
}
build(U, V, A, B);
return 1;
}
