#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
typedef long long ll;
ll n;
vector<ll> lnk;
vector<ll> sz;
ll find(ll a) {
if (a != lnk[a]) lnk[a] = find(lnk[a]);
return lnk[a];
}
bool unite(ll a, ll b) {
a = find(a); b = find(b);
if (a == b) return false;
if (sz[a] > sz[b]) swap(a, b);
lnk[a] = b;
sz[b] += sz[a];
return true;
}
int construct_roads(vector<int> x, vector<int> y) {
n = x.size();
lnk = vector<ll>(n);
sz = vector<ll>(n, 1);
for (int i = 0; i < n; i++) lnk[i] = i;
unordered_map<ll, ll> pts;
vector<pair<ll, ll>> edges;
unordered_set<ll> hasEdge;
for (int i = 0; i < n; i++) {
ll hash = ((ll)x[i] << 31) | (ll)y[i];
pts[hash] = i;
}
for (ll i = 0; i < n; i++) {
ll hashL = (((ll)x[i]-2) << 31) | ((ll)y[i]);
if (pts.count(hashL)) {
ll hash = (min(i, pts[hashL]) << 31) | max(i, pts[hashL]);
if (!hasEdge.count(hash)) {
edges.push_back({i, pts[hashL]});
hasEdge.insert(hash);
}
}
ll hashR = (((ll)x[i]+2) << 31) | ((ll)y[i]);
if (pts.count(hashR)) {
ll hash = (min(i, pts[hashR]) << 31) | max(i, pts[hashR]);
if (!hasEdge.count(hash)) {
edges.push_back({i, pts[hashR]});
hasEdge.insert(hash);
}
}
ll hashD = (((ll)x[i]) << 31) | ((ll)y[i]-2);
if (pts.count(hashD)) {
ll hash = (min(i, pts[hashD]) << 31) | max(i, pts[hashD]);
if (!hasEdge.count(hash)) {
edges.push_back({i, pts[hashD]});
hasEdge.insert(hash);
}
}
ll hashU = (((ll)x[i]) << 31) | ((ll)y[i]+2);
if (pts.count(hashU)) {
ll hash = (min(i, pts[hashU]) << 31) | max(i, pts[hashU]);
if (!hasEdge.count(hash)) {
edges.push_back({i, pts[hashU]});
hasEdge.insert(hash);
}
}
}
vector<int> u, v, a, b;
for (auto &e : edges) {
unite(e.first, e.second);
u.push_back(e.first);
v.push_back(e.second);
if (x[e.first] == 2 && x[e.second] == 2) {
a.push_back(1);
b.push_back((y[e.first] + y[e.second]) / 2);
}
else if (x[e.first] == 4 && x[e.second] == 4) {
a.push_back(5);
b.push_back((y[e.first] + y[e.second]) / 2);
}
else {
a.push_back(3);
b.push_back(y[e.first] + 1);
}
}
if (sz[find(0)] < n) return 0;
build(u, v, a, b);
return 1;
}
