//Challenge: Accepted
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
vector<pii> xv[maxn], yv[maxn];
unordered_map<ll, vector<ll> > g;
unordered_set<ll> bad;
unordered_map<ll, bool> vis;
vector<ll> outside;
ll h(int x, int y) {
return (ll)x * maxn + y;
}
struct DSU{
int par[maxn];
int merges = 0;
void init(int n) {
for (int i = 0;i < n;i++) par[i] = i;
}
int find(int a) {
return a == par[a] ? a : (par[a] = find(par[a]));
}
void Union(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
merges++;
par[a] = b;
}
} dsu;
vector<int> u, v, a, b;
void dfs(ll n) {
vis[n] = 1;
for (auto p:g[n]) {
if (!vis[p]) {
int vx = (p / maxn + n / maxn) / 2, vy = (p % maxn + n % maxn) / 2;
bad.insert(h(vx, vy));
dfs(p);
}
}
}
unordered_set<ll> vert, block;
int construct_roads(std::vector<int> X, std::vector<int> Y) {
int n = X.size();
dsu.init(n);
for (int i = 0;i < n;i++) {
xv[X[i]].push_back({Y[i], i});
yv[Y[i]].push_back({X[i], i});
vert.insert(h(X[i], Y[i]));
}
auto found = [&] (int x, int y){
return vert.find(h(x, y)) != vert.end();
};
for (auto i:vert) {
int x = i / maxn, y = i % maxn;
if (found(x+2, y) && found(x+2, y+2) && found(x, y+2)) {
block.insert(h(x+1, y+1));
}
}
for (auto i:block) {
int x = i / maxn, y = i % maxn;
if ((x + y) % 4) {
g[h(x+2, y)].push_back(i);
g[h(x-2, y)].push_back(i);
if (block.find(h(x+2, y)) == block.end()) {
outside.push_back(h(x+2, y));
}
if (block.find(h(x-2, y)) == block.end()) {
outside.push_back(h(x-2, y));
}
} else {
g[h(x, y+2)].push_back(i);
g[h(x, y-2)].push_back(i);
if (block.find(h(x, y+2)) == block.end()) {
outside.push_back(h(x, y+2));
}
if (block.find(h(x, y-2)) == block.end()) {
outside.push_back(h(x, y-2));
}
}
}
for (auto i:outside) dfs(i);
for (int i = 0;i < maxn;i += 2) {
sort(xv[i].begin(), xv[i].end());
sort(yv[i].begin(), yv[i].end());
for (int j = 0;j < (int)xv[i].size() - 1;j++) {
if (xv[i][j].ff + 2 == xv[i][j+1].ff) {
dsu.Union(xv[i][j].ss, xv[i][j+1].ss);
if (bad.find(h(i, xv[i][j].ff + 1)) != bad.end()) continue;
u.push_back(xv[i][j].ss);
v.push_back(xv[i][j+1].ss);
b.push_back(xv[i][j].ff + 1);
if ((xv[i][j].ff + i + 2) % 4) {
a.push_back(i+1);
} else {
a.push_back(i-1);
}
}
}
for (int j = 0;j < (int)yv[i].size() - 1;j++) {
if (yv[i][j].ff + 2 == yv[i][j+1].ff) {
dsu.Union(yv[i][j].ss, yv[i][j+1].ss);
if (bad.find(h(yv[i][j].ff + 1, i)) != bad.end()) continue;
u.push_back(yv[i][j].ss);
v.push_back(yv[i][j+1].ss);
a.push_back(yv[i][j].ff + 1);
if ((yv[i][j].ff + i) % 4) {
b.push_back(i+1);
} else {
b.push_back(i-1);
}
}
}
}
if (dsu.merges != n - 1) return 0;
build(u, v, a, b);
return 1;
}
