#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) int((x).size())
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
struct DSU {
int n; vi par;
DSU(int N = 0) : n(N), par(N, -1) {}
int find(int v) {return par[v] == -1 ? v : par[v] = find(par[v]);}
void unite(int a, int b) {if (find(a) != find(b)) par[find(b)] = find(a);}
};
bool validate(int n, int m, vi x, vi y, vi u, vi v, vi a, vi b) {
auto dsu = DSU(n);
for (int i = 0; i < m; i++) dsu.unite(u[i], v[i]);
bool good = true; int d = dsu.find(0);
for (int i = 1; i < n; i++) good = good && dsu.find(i) == d;
set<pi> bench;
for (int i = 0; i < m; i++) {
set<pi> e({{a[i]-1, b[i]-1}, {a[i]-1, b[i]+1}, {a[i]+1, b[i]-1}, {a[i]+1, b[i]+1}});
pi ea = {x[u[i]], y[u[i]]}, eb = {x[v[i]], y[v[i]]};
good = good && ea != eb && e.count(ea) && e.count(eb);
good = good && !bench.count({a[i], b[i]});
good = good && a[i] != -1 && b[i] != -1;
bench.insert({a[i], b[i]});
}
return good;
}
int construct_roads(vi x, vi y) {
int n = sz(x);
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
vector<int> isrt(n); iota(all(isrt), 0);
sort(all(isrt), [&](int i, int j) {return make_pair(x[i], y[i]) < make_pair(x[j], y[j]);});
vi rm(n); for (int i = 0; i < n; i++) rm[isrt[i]] = i;
map<pi, int> cmap;
for (int i = 0; i < n; i++) cmap[{x[i], y[i]}] = i;
int m = 0;
vi u, v, a, b;
auto dsu = DSU(n);
set<pi> used;
// map<pi, set<int>> bridgemap;
// map<int, set<pi>> otherway;
for (int dx = 0; dx < n; dx++) {
int idx = isrt[dx];
int i = x[idx], j = y[idx];
// if (j >= 82680 && j <= 82690) cout << "(" << i << "," << j << ")\n";
for (auto &[di, dj] : vector<pi>({{0, -2}, {-2, 0}})) {
if (di == 0 && dj == 0) continue;
if (di != 0 && dj != 0) continue;
if (!cmap.count({i+di, j+dj})) continue;
int node2 = cmap[{i+di, j+dj}];
// if (dsu.find(idx) == dsu.find(node2)) continue;
pi f;
if (di == 0 && dj == -2) f = {(((i+j)/2)%2==0 ? i+1 : i-1), j-1};
else if (di == -2 && dj == 0) f = {i-1, (((i+j)/2)%2==0 ? j-1 : j+1)};
if (used.count(f)) continue;
used.insert(f);
int id = m++;
// swap(f.first, f.second); swap(g.first, g.second);
// cerr << "Road between (" << i << "," << j << ") and (" << i+di << "," << j+dj << ") with benches (" << f.first << "," << f.second << ") and (" << g.first << "," << g.second << ")\n";
u.push_back(idx), v.push_back(node2); a.push_back(f.first), b.push_back(f.second);
dsu.unite(idx, node2);
}
}
int d = dsu.find(0);
for (int i = 1; i < n; i++) {
if (dsu.find(i) != d) return 0;
}
// a.assign(m, -1); b.assign(m, -1);
// queue<pi> q;
// for (auto &[k, s] : bridgemap) {
// if (sz(bridgemap[k]) == 1) q.push(k);
// }
// while (!q.empty()) {
// pi cur = q.front(); q.pop();
// if (sz(bridgemap[cur]) != 1) continue;
// int tm = *bridgemap[cur].begin();
// // cerr << "(" << u[tm] << "," << v[tm] << ") has a neighbour: (" << cur.first << "," << cur.second << ")\n";
// a[tm] = cur.first, b[tm] = cur.second;
// for (auto pot : otherway[tm]) {
// bridgemap[pot].erase(tm);
// }
// for (auto road : bridgemap[cur]) {
// otherway[road].erase(cur);
// }
// bridgemap[cur].clear();
// for (auto pot : otherway[tm]) {
// if (sz(bridgemap[pot]) == 1) q.push(pot);
// }
// otherway[tm].clear();
// }
// int n1 = m, n2 = 0;
// map<pi, int> id; map<int, pi> revid; for (auto &[k, s] : bridgemap) {
// id[k] = n2++; revid[id[k]] = k;
// }
// vvi L(n1, vi()), R(n2, vi()); vi matched(n2, 0);
// for (auto &[k, s] : bridgemap) for (auto &node : s) R[id[k]].push_back(node), L[node].push_back(id[k]);
// // for (auto &[k, s] : otherway) for (auto &node : s) L[k].push_back(id[node]);
// // for (int i = 0; i < m; i++) {
// // cerr << "Road " << i << " has edges to benches: ";
// // for (auto &k : L[i]) cerr << k << " ";
// // cerr << "\n";
// // }
// set<int> seen;
// for (int i = 0; i < n1; i++) {
// if (seen.count(i)) continue;
// queue<int> q; q.push(i); seen.insert(i);
// while (!q.empty()) {
// int u = q.front(); q.pop();
// for (auto v : L[u]) {
// int v2 = R[v][0] == u ? R[v][1] : R[v][0];
// if (!matched[v]) {
// matched[v] = 1;
// a[u] = revid[v].first, b[u] = revid[v].second;
// } else {
// continue;
// }
// if (seen.count(v2)) continue;
// seen.insert(v2);
// q.push(v2);
// break;
// }
// }
// }
if (!validate(n, m, x, y, u, v, a, b)) {
cerr << "The structure is invalid!\n";
return 0;
}
build(u, v, a, b);
return 1;
}
