#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
struct DSU {
vt<int> uf;
DSU(const int n) : uf(n, -1) {}
int find(const int i) {
return uf[i] < 0 ? i : uf[i] = find(uf[i]);
}
bool unite(int a, int b) {
if ((a = find(a)) == (b = find(b)))
return false;
if (uf[a] > uf[b])
swap(a, b);
uf[a] += uf[b];
uf[b] = a;
return true;
}
};
constexpr int dir[5] = {2, 0, -2, 0, 2};
struct Edge {
int to, cap, flow, ind;
};
struct Dinic {
const int N;
vt<vt<Edge>> adj;
vt<int> dist, ptr;
Dinic(const int n) : N(n), adj(n), dist(n), ptr(n) {}
void add_edge(const int a, const int b, const int c) {
adj[a].push_back({b, c, 0, size(adj[b])});
adj[b].push_back({a, 0, 0, size(adj[a]) - 1});
}
bool bfs() {
fill(all(dist), N);
dist[0] = 0;
queue<int> qu;
qu.push(0);
while (size(qu)) {
const int i = qu.front();
qu.pop();
for (const auto &[j, cap, flow, ind] : adj[i])
if (cap - flow > 0 && dist[i] + 1 < dist[j]) {
dist[j] = dist[i] + 1;
qu.push(j);
}
}
return dist[N-1] < N;
}
int dfs(const int i, const int F) {
if (!F)
return 0;
if (i == N-1)
return F;
for (; ptr[i] < size(adj[i]); ptr[i]++) {
auto &[j, cap, flow, ind] = adj[i][ptr[i]];
if (dist[i] + 1 != dist[j])
continue;
const int v = dfs(j, min(F, cap - flow));
if (v) {
flow += v;
adj[j][ind].flow -= v;
return v;
}
}
return 0;
}
vt<ari2> solve() {
while (bfs()) {
fill(all(ptr), 0);
while (dfs(0, INT_MAX));
}
vt<ari2> pairs;
FOR(i, 1, N-2)
for (const auto &[j, cap, flow, ind] : adj[i])
if (flow == 1 && j != N-1)
pairs.push_back({i, j});
return pairs;
}
};
int construct_roads(vt<int> X, vt<int> Y) {
const int N = size(X);
map<ari2, int> points;
vt<ari2> edges;
FOR(i, 0, N-1) {
FOR(j, 0, 3) {
const int x = X[i] + dir[j];
const int y = Y[i] + dir[j+1];
if (points.find({x, y}) != points.end()) {
const int k = points[{x, y}];
edges.push_back({i, k});
}
}
points[{X[i], Y[i]}] = i;
}
if (*max_element(all(X)) <= 6) {
DSU uf(N);
vt<int> A, B, C, D;
vt<ari3> fours;
for (const auto &[i, j] : edges) {
if (X[i] == X[j]) {
uf.unite(i, j);
if (X[i] == 2) {
A.push_back(i);
B.push_back(j);
C.push_back(1);
D.push_back(Y[i] + Y[j] >> 1);
} else if (X[i] == 6) {
A.push_back(i);
B.push_back(j);
C.push_back(7);
D.push_back(Y[i] + Y[j] >> 1);
} else {
fours.push_back({Y[i] + Y[j] >> 1, i, j});
}
}
}
sort(all(fours));
int add = 1;
set<ari2> have;
for (const auto &[_, i, j] : fours) {
A.push_back(i);
B.push_back(j);
C.push_back(4 + add);
D.push_back(Y[i] + Y[j] >> 1);
have.insert({4 + add, Y[i] + Y[j] >> 1});
add *= -1;
}
for (const auto &[i, j] : edges) {
if (Y[i] == Y[j]) {
if (!uf.unite(i, j))
continue;
A.push_back(i);
B.push_back(j);
const int x = X[i] + X[j] >> 1;
C.push_back(x);
if (have.count({x, Y[i] + 1})) {
assert(!have.count({x, Y[i] - 1}));
have.insert({x, Y[i] - 1});
D.push_back(Y[i] - 1);
} else {
have.insert({x, Y[i] + 1});
D.push_back(Y[i] + 1);
}
}
}
assert(size(A) == size(B) && size(B) == size(C) && size(C) == size(D));
if (size(A) != N - 1)
return 0;
build(A, B, C, D);
return 1;
}
DSU uf(N);
vt<ari2> used;
FOR(x, 0, size(edges) - 1) {
auto &[i, j] = edges[x];
if (!uf.unite(i, j))
continue;
if (i > j)
swap(i, j);
used.push_back({i, j});
}
if (size(used) != N - 1)
return 0;
map<ari2, int> benches;
vt<ari2> benches2;
int M = 0;
for (const auto &[i, j] : used) {
const auto check = [&](const ari2 b) {
if (benches.find(b) != benches.end())
return;
benches[b] = M++;
benches2.push_back(b);
};
if (X[i] == X[j]) {
check({X[i] - 1, Y[i] + Y[j] >> 1});
check({X[i] + 1, Y[i] + Y[j] >> 1});
} else {
check({X[i] + X[j] >> 1, Y[i] - 1});
check({X[i] + X[j] >> 1, Y[i] + 1});
}
}
Dinic flow(N+M+1);
int cur = 0;
FOR(x, 0, N-2) {
flow.add_edge(0, x + 1, 1);
const auto &[i, j] = used[x];
const auto check = [&](const ari2 b) {
flow.add_edge(x + 1, benches[b] + N, 1);
};
if (X[i] == X[j]) {
check({X[i] - 1, Y[i] + Y[j] >> 1});
check({X[i] + 1, Y[i] + Y[j] >> 1});
} else {
check({X[i] + X[j] >> 1, Y[i] - 1});
check({X[i] + X[j] >> 1, Y[i] + 1});
}
}
FOR(i, N, N+M-1)
flow.add_edge(i, N+M, 1);
vt<ari2> pairs = flow.solve();
if (size(pairs) != N - 1)
return 0;
vt<int> A, B, C, D;
for (auto &[i, j] : pairs) {
i--, j -= N;
A.push_back(used[i][0]);
B.push_back(used[i][1]);
C.push_back(benches2[j][0]);
D.push_back(benches2[j][1]);
}
build(A, B, C, D);
return 1;
}
