#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> e;
DSU (int n) {
e = vector<int>(n, -1);
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
int size(int x) {
return -e[get(x)];
}
bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
vector<vector<int>> adj;
vector<int> matched_to;
int idx;
bool try_kuhn(int v, vector<bool> &visited, vector<int> &matched_to) {
if (visited.at(v)) return false;
visited.at(v) = true;
for (int to : adj.at(v)) {
if (matched_to.at(to) == -1 || try_kuhn(matched_to.at(to), visited, matched_to)) {
matched_to.at(to) = v;
return true;
}
}
return false;
}
int bipartite_matching(int n) {
int matches = 0;
for (int i = idx; i < n; i++) {
vector<bool> visited = vector<bool>(n, false);
if (try_kuhn(i, visited, matched_to)) {
matches += 1;
}
}
return matches;
}
void add_edge(int i, int j) {
adj[i].push_back(j);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int N = x.size();
const int MAXN = 2e5;
vector<map<int, int>> mp(MAXN + 10);
for (int i = 0; i < N; ++i) {
mp[x[i]][y[i]] = i;
}
idx = N;
vector<map<int, int>> pl(MAXN + 10);
vector<array<int, 2>> rev;
vector<int> dx = {1, 1, -1, -1}, dy = {1, -1, 1, -1};
vector<array<int, 2>> edges;
for (int i = 0; i < N; ++i) {
for (int k = 0; k < 4; ++k) {
int nx = x[i] + dx[k];
int ny = y[i] + dy[k];
if (!pl[nx].count(ny)) {
pl[nx][ny] = idx++;
rev.push_back({nx, ny});
}
}
}
for (int i = 0; i < N; ++i) {
if (mp[x[i]].count(y[i] + 2)) {
edges.push_back({i, mp[x[i]][y[i] + 2]});
}
if (mp[x[i] + 2].count(y[i])) {
edges.push_back({i, mp[x[i] + 2][y[i]]});
}
}
adj.resize(edges.size() + idx + 1);
matched_to = vector<int>(edges.size() + idx + 1, -1);
for (int it = 0; it < edges.size(); ++it) {
int i = edges[it][0];
int j = edges[it][1];
if (x[i] == x[j]) {
int ny = y[i] + 1;
int nx = x[i] + 1;
assert(pl[nx].count(ny));
int index = pl[nx][ny];
add_edge(it + idx, index);
nx = x[i] - 1;
assert(pl[nx].count(ny));
index = pl[nx][ny];
add_edge(it + idx, index);
} else {
assert(y[i] == y[j]);
int ny = y[i] + 1;
int nx = x[i] + 1;
assert(pl[nx].count(ny));
int index = pl[nx][ny];
add_edge(it + idx, index);
ny = y[i] - 1;
assert(pl[nx].count(ny));
index = pl[nx][ny];
add_edge(it + idx, index);
}
}
// cout << N << "\n";
// for (int it = 0; it < idx + edges.size(); ++it) {
// cout << it << ": ";
// for (auto& u : adj[it]) {
// cout << u << " ";
// }
// cout << "\n";
// }
// cerr << endl;
int matches = bipartite_matching(edges.size() + idx + 1);
if (matches != (int)edges.size()) return 0;
vector<int> u, v, a, b;
for (int it = N; it < idx; ++it) {
// cout << matched_to[it] << " ";
if (matched_to[it] == -1) continue;
int i = edges[matched_to[it] - idx][0];
int j = edges[matched_to[it] - idx][1];
int nx = rev[it - N][0];
int ny = rev[it - N][1];
u.push_back(i);
v.push_back(j);
a.push_back(nx);
b.push_back(ny);
}
// cout << "\n";
// for (int it = 0; it < edges.size(); ++it) {
// int I = it + idx;
// int J = matched_to[I];
// assert(J != -1);
// }
build(u, v, a, b);
return 1;
}
