#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;
}
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);
map<pi, set<int>> bridgemap;
map<int, set<pi>> otherway;
for (int idx = 0; idx < n; idx++) {
int i = x[idx], j = y[idx];
for (int di = -2; di <= 2; di += 2) {
for (int dj = -2; dj <= 2; dj += 2) {
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;
int id = m++;
pi f, g;
if (di == 0 && dj == 2) f = {i-1, j+1}, g = {i+1, j+1};
else if (di == 0 && dj == -2) f = {i-1, j-1}, g = {i+1, j-1};
else if (di == 2 && dj == 0) f = {i+1, j-1}, g = {i+1, j+1};
else if (di == -2 && dj == 0) f = {i-1, j-1}, g = {i-1, j+1};
// 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";
bridgemap[f].insert(id); bridgemap[g].insert(id);
otherway[id].insert(f); otherway[id].insert(g);
u.push_back(idx), v.push_back(node2);
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;
}
