#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '['; string sep = ""; for (const auto &x : v) os << sep << x, sep = ", "; return os << ']'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename A> ostream& operator<<(ostream &os, const set<A> &s) { os << '{'; string sep = ""; for (const auto &x : s) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const map<A, B> &m) { os << '{'; string sep = ""; for (const auto &x : m) os << sep << x.first << " -> " << x.second, sep = ", "; return os << '}'; }
void debug() { cerr << endl; }
template<typename Ini, typename... Fim> void debug(Ini I, Fim... F) { cerr << I; if(sizeof...(F)) cerr << ", "; debug(F...);}
#define db(...) cerr << "DEBUG (" << #__VA_ARGS__ << ") == ", debug(__VA_ARGS__)
#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(),(a).end()
#define ff first
#define ss second
constexpr int inf = 0x3f3f3f3f;
constexpr int maxn = 8e5 + 10;
mt19937 rng(random_device{}());
struct DSU {
int pai[maxn], peso[maxn], qtd;
DSU() { for(int i = 0; i < maxn; i++) pai[i] = i, peso[i] = 1; }
int find(int x) { return pai[x] == x ? x : pai[x] = find(pai[x]); }
void join(int a, int b) {
a = find(a), b = find(b);
if(a == b) return;
--qtd;
if(peso[a] < peso[b]) swap(a, b);
pai[b] = a;
peso[a] += peso[b];
}
} dsu;
vector<int> pt[maxn], g[maxn];
int match[maxn];
bool mark[maxn];
int t, n, qtd_ruas;
bool dfs(int u) {
mark[u] = 1;
if(u >= qtd_ruas) return (match[u] == -1 ? 1 : dfs(match[u]));
for(int v : g[u]) {
if(mark[v] || !dfs(v)) continue;
match[u] = v; match[v] = u;
return 1;
}
return 0;
}
struct Road { // todas as ruas possiveis
int x, y, tipo; // ponto inicial da rua e se é vertical ou horizontal
} ruas[maxn];
pii conecta[maxn];
struct Banco {
int x, y;
} bancos[maxn];
map<pair<int,int>, int> mp; // salva o id dos pontos
inline void add(int a, int b) { g[a].pb(b), g[b].pb(a); }
int get(pii p) {
if(mp.count(p)) return mp[p];
bancos[t] = {p.ff, p.ss};
return mp[p] = t++;
}
int construct_roads(vector<int> x, vector<int> y) {
n = sz(x); dsu.qtd = n;
for(int i = 0; i < n; i++)
mp[pii(x[i], y[i])] = i;
for(int i = 0; i < n; i++) {
if(mp.count({x[i]+2, y[i]})) {
conecta[t] = {i, mp[pii(x[i]+2, y[i])]};
ruas[t++] = {x[i], y[i], 0}; // 0 == horizontal
dsu.join(i, mp[pii(x[i]+2, y[i])]);
}
if(mp.count({x[i], y[i]+2})) {
conecta[t] = {i, mp[pii(x[i], y[i]+2)]};
ruas[t++] = {x[i], y[i], 1}; // 1 == vertical
dsu.join(i, mp[pii(x[i], y[i]+2)]);
}
}
if(dsu.qtd != 1) return 0; // impossivel, o grafo completo não é conexo
qtd_ruas = t;
for(int i = 0; i < qtd_ruas; i++) {
auto [X, Y, tipo] = ruas[i];
// db(X, Y, tipo);
if(!tipo) {
int aq = get({X+1, Y+1});
add(i, aq);
// db(pii(X, Y), tipo, aq);
aq = get({X+1, Y-1});
add(i, aq);
// db(pii(X, Y), tipo, aq);
} else {
int aq = get({X+1, Y+1});
add(i, aq);
// db(pii(X, Y), tipo, aq);
aq = get({X-1, Y+1});
add(i, aq);
// db(pii(X, Y), tipo, aq);
}
}
int ans = 0;
memset(match, -1, sizeof match);
vector<int> p(qtd_ruas); iota(all(p), 0);
for(int i = 0; i < t; i++)
shuffle(all(g[i]), rng);
for(int antes = -1; ans != antes;) {
antes = ans;
memset(mark, 0, sizeof mark);
shuffle(all(p), rng);
for(int i = 0; i < qtd_ruas; i++)
if(!mark[p[i]] && match[p[i]] == -1 && dfs(p[i])) ++ans;
// db("OPA", ans, antes);
}
// db(ans);
/* for(int i = 0; i < qtd_ruas; i++)
db(i, match[i], bancos[match[i]].x, bancos[match[i]].y); */
if(ans != qtd_ruas) return 0;
vector<int> u(qtd_ruas), v(qtd_ruas), a(qtd_ruas), b(qtd_ruas);
for(int i = 0; i < qtd_ruas; i++) {
u[i] = conecta[i].ff, v[i] = conecta[i].ss;
a[i] = bancos[match[i]].x, b[i] = bancos[match[i]].y;
}
build(u, v, a, b);
return 1;
}
