#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int nmax = 2e5 + 5;
using pii = pair<int,int>;
#define sz(x) ((int)(x).size())
map<pii, int> encr;
map<int, pii> decr;
vector<int> g[nmax];
int dirx[4] = {-2, 2, 0, 0}, diry[4] = {0, 0, 2, -2};
int occ[nmax];
vector<pii> edges;
void dfs(int node) {
occ[node] = 1;
for(auto x : g[node]) {
if(occ[x]) continue;
edges.emplace_back(node, x);
dfs(x);
}
return;
}
pair<vector<int>, vector<int>> unravel(vector<pii>& v) {
vector<int> a, b;
for(auto [x, y] : v) a.emplace_back(x), b.emplace_back(y);
return make_pair(a, b);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
for(int i = 0; i < sz(x); i++)
encr[make_pair(x[i], y[i])] = i;
for(auto [a, b] : encr) {
decr[b] = a;
for(int i = 0; i < 4; i++) {
if(encr.count(make_pair(a.first + dirx[i], a.second + diry[i])))
g[b].emplace_back(encr[make_pair(a.first + dirx[i], a.second + diry[i])]);
}
}
dfs(0);
if([&]() {
for(int i = 0; i < sz(x); i++) if(occ[i] == 0) return 1;
return 0;
}()) { return 0; }
map<pii, unordered_set<int>> adj;
vector<pii> avail[5];
for(int i = 0; i < sz(edges); i++) {
auto [x1, y1] = decr[edges[i].first];
auto [x2, y2] = decr[edges[i].second];
if(x1 == x2) {
adj[make_pair(x1 + 1, max(y1, y2) - 1)].emplace(i);
adj[make_pair(x1 - 1, max(y1, y2) - 1)].emplace(i);
}
else {
assert(y1 == y2);
adj[make_pair(max(x1, x2) - 1, y1 - 1)].emplace(i);
adj[make_pair(max(x1, x2) - 1, y1 + 1)].emplace(i);
}
}
for(auto [a, b] : adj) { avail[sz(b)].emplace_back(a); }
vector<pii> assoc(sz(edges));
auto get_top = [&]() {
for(int plane = 1; plane <= 4; plane++) {
while(avail[plane].size()) {
auto a = avail[plane].back();
avail[plane].pop_back();
if(adj.count(a)) return a;
}
}
assert(false);
};
for(int it = 0; it < sz(edges); it++) {
auto T = get_top();
//cerr << T.first << ' ' << T.second << '\t';
int idx = *adj[T].begin();
//cerr << idx << '\n';
{
auto [x1, y1] = decr[edges[idx].first];
auto [x2, y2] = decr[edges[idx].second];
if(x1 == x2) {
auto _1 = make_pair(x1 - 1, max(y1, y2) - 1), _2 = make_pair(x1 + 1, max(y1, y2) - 1);
adj[_1].erase(idx);
adj[_2].erase(idx);
avail[sz(adj[_1])].emplace_back(_1);
avail[sz(adj[_2])].emplace_back(_2);
}
else {
assert(y1 == y2);
auto _1 = make_pair(max(x1, x2) - 1, y1 + 1), _2 = make_pair(max(x1, x2) - 1, y1 - 1);
adj[_1].erase(idx);
adj[_2].erase(idx);
avail[sz(adj[_1])].emplace_back(_1);
avail[sz(adj[_2])].emplace_back(_2);
}
}
adj.erase(T);
assoc[idx] = T;
}
auto [yi, er] = unravel(edges);
auto [san, si] = unravel(assoc);
build(yi, er, san, si);
return 1;
}
