#include <bits/stdc++.h>
#include "parks.h"
struct Flow {
static constexpr int INF = 1e9;
int n;
struct Edge {
int to, cap;
Edge(int to, int cap) : to(to), cap(cap) {}
};
std::vector<Edge> e;
std::vector<std::vector<int>> g;
std::vector<int> cur, h;
Flow(int n) : n(n), g(n) {}
bool bfs(int s, int t) {
h.assign(n, -1);
std::queue<int> que;
h[s] = 0;
que.push(s);
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i : g[u]) {
auto [v, c] = e[i];
if (c > 0 && h[v] == -1) {
h[v] = h[u] + 1;
if (v == t)
return true;
que.push(v);
}
}
}
return false;
}
int dfs(int u, int t, int f) {
if (u == t)
return f;
int r = f;
for (int &i = cur[u]; i < int(g[u].size()); ++i) {
int j = g[u][i];
auto [v, c] = e[j];
if (c > 0 && h[v] == h[u] + 1) {
int a = dfs(v, t, std::min(r, c));
e[j].cap -= a;
e[j ^ 1].cap += a;
r -= a;
if (r == 0)
return f;
}
}
return f - r;
}
void addEdge(int u, int v, int c) {
g[u].push_back(e.size());
e.emplace_back(v, c);
g[v].push_back(e.size());
e.emplace_back(u, 0);
}
int maxFlow(int s, int t) {
int ans = 0;
while (bfs(s, t)) {
cur.assign(n, 0);
ans += dfs(s, t, INF);
}
return ans;
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
std::map<std::pair<int, int>, int> id;
for (int i = 0; i < n; i++) {
id[{x[i], y[i]}] = i;
}
std::vector<bool> vis(n);
vis[0] = true;
std::stack<int> stk;
stk.push(0);
std::vector<std::pair<int, int>> edges;
while (!stk.empty()) {
int u = stk.top();
stk.pop();
for (auto move : {std::make_pair(0, -2), {-2, 0}, {0, 2}, {2, 0}}) {
int x0 = x[u] + move.first;
int y0 = y[u] + move.second;
if (!id.count({x0, y0})) {
continue;
}
int v = id[{x0, y0}];
if (!vis[v]) {
edges.emplace_back(u, v);
vis[v] = true;
stk.push(v);
}
}
}
if (int(edges.size()) < n - 1) {
return 0;
}
std::map<std::pair<int, int>, int> id2;
std::vector<std::pair<int, int>> matches;
std::vector<std::pair<int, int>> pts;
auto add = [&](int u, int x, int y) {
if (!id2.count({x, y})) {
id2[{x, y}] = pts.size();
pts.emplace_back(x, y);
}
matches.emplace_back(u, id2[{x, y}]);
};
for (int i = 0; i < n - 1; i++) {
auto [u, v] = edges[i];
if (x[u] == x[v]) {
add(i, x[u] - 1, (y[u] + y[v]) / 2);
add(i, x[u] + 1, (y[u] + y[v]) / 2);
} else {
add(i, (x[u] + x[v]) / 2, y[u] - 1);
add(i, (x[u] + x[v]) / 2, y[u] + 1);
}
}
Flow g(n + 1 + pts.size());
int S = n - 1, T = n + pts.size();
for (auto [u, v] : matches) {
g.addEdge(u, n + v, 1);
}
for (int i = 0; i < n - 1; i++) {
g.addEdge(S, i, 1);
}
for (int i = 0; i < int(pts.size()); i++) {
g.addEdge(n + i, T, 1);
}
assert(g.maxFlow(S, T) == n - 1);
std::vector<int> U, V, A, B;
for (int i = 0; i < int(matches.size()); i++) {
if (!g.e[2 * i].cap) {
auto [j, k] = matches[i];
U.push_back(edges[j].first);
V.push_back(edges[j].second);
A.push_back(pts[k].first);
B.push_back(pts[k].second);
}
}
build(U, V, A, B);
return 1;
}
