#include "parks.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<lint, lint>;
const int MAXN = 400005;
const int mod = 1e9 + 7;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
struct point{
int x, y, idx;
};
struct disj{
int pa[MAXN];
void init(int n){
iota(pa, pa + n, 0);
}
int find(int x){
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[q] = p; return 1;
}
}disj;
bool vis[MAXN];
int V = 0, E = 0;
vector<int> dfn;
vector<pi> gph[MAXN];
void dfs(int x){
if(vis[x]) return;
vis[x] = 1;
dfn.push_back(x);
V += 1;
E += sz(gph[x]);
for(auto &[_, y] : gph[x]) dfs(y);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = sz(x);
vector<point> p;
vector<pi> edges;
vector<pi> matches;
vector<pi> to_mst;
auto get_mode = [&](pi q){
int x = q.first, y = q.second;
int val = (p[y].x + p[y].y) % 4;
if(val % 4 == 0) return p[x].x == p[y].x ? 0 : 2;
return p[x].x == p[y].x ? 1 : 3;
};
for(int i = 0; i < n; i++){
p.push_back({x[i], y[i], i});
}
sort(all(p), [&](const point &a, const point &b){
return pi(a.x, a.y) < pi(b.x, b.y);
});
disj.init(n);
for(int i = 1; i < sz(p); i++){
if(p[i-1].x == p[i].x && p[i-1].y + 2 == p[i].y){
to_mst.emplace_back(p[i-1].idx, p[i].idx);
}
}
sort(all(p), [&](const point &a, const point &b){
return pi(a.y, a.x) < pi(b.y, b.x);
});
for(int i = 1; i < sz(p); i++){
if(p[i-1].y == p[i].y && p[i-1].x + 2 == p[i].x){
to_mst.emplace_back(p[i-1].idx, p[i].idx);
}
}
sort(all(p), [&](const point &a, const point &b){
return a.idx < b.idx;
});
sort(all(to_mst), [&](const pi &x, const pi &y){
return get_mode(x) < get_mode(y);
});
for(auto &[x, y] : to_mst){
if(disj.uni(x, y)) edges.emplace_back(x, y);
}
if(sz(edges) != n - 1) return 0;
map<pi, int> mp;
vector<int> U, _V, A(n-1), B(n-1);
for(auto &[x, y] : edges){
U.push_back(x);
_V.push_back(y);
set<pi> s;
int mx = (p[x].x + p[y].x) / 2;
int my = (p[x].y + p[y].y) / 2;
for(int i = 0; i < 4; i++){
s.emplace(mx + dx[i], my + dy[i]);
}
s.erase(pi(p[x].x, p[x].y));
s.erase(pi(p[y].x, p[y].y));
for(auto &p : s){
if(mp.find(p) == mp.end()){
int idx = sz(mp);
mp[p] = idx;
}
}
matches.emplace_back(mp[*s.begin()], mp[*s.rbegin()]);
}
vector<int> deg(sz(mp));
for(int i = 0; i < sz(matches); i++){
int x, y; tie(x, y) = matches[i];
gph[x].emplace_back(i, y);
gph[y].emplace_back(i, x);
deg[x]++;
deg[y]++;
}
vector<pi> mrev(sz(mp));
for(auto &[x, y] : mp){
mrev[y] = x;
}
for(int i = 0; i < sz(mp); i++){
if(!vis[i]){
V = E = 0;
dfn.clear();
dfs(i);
E /= 2;
if(V < E){
return 0;
}
assert(V >= E);
queue<int> que;
for(auto &v : dfn){
if(deg[v] == 1){
que.push(v);
}
}
while(sz(que)){
int x = que.front();
que.pop();
for(auto &[i, y] : gph[x]){
if(!deg[y]) continue;
deg[x]--;
deg[y]--;
A[i] = mrev[x].first;
B[i] = mrev[x].second;
// printf("%d %d\n", i, x);
if(deg[y] == 1){
que.push(y);
}
}
}
if(V != E) continue;
for(auto &v : dfn){
if(deg[v] == 2){
int I, V, W;
for(auto &[i, w] : gph[v]){
if(deg[w] == 2){
deg[v]--;
deg[w]--;
tie(I, V, W) = make_tuple(i, v, w);
break;
}
}
gph[V].erase(find(all(gph[V]), pi(I, W)));
gph[W].erase(find(all(gph[W]), pi(I, V)));
// printf("%d %d\n", I, W);
A[I] = mrev[W].first;
B[I] = mrev[W].second;
que.push(V);
break;
}
}
while(sz(que)){
int x = que.front();
que.pop();
for(auto &[i, y] : gph[x]){
if(!deg[y]) continue;
deg[x]--;
deg[y]--;
// printf("%d %d\n", i, x);
A[i] = mrev[x].first;
B[i] = mrev[x].second;
if(deg[y] == 1){
que.push(y);
}
}
}
}
}
build(U, _V, A, B);
return 1;
}
