#include "parks.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
using namespace std;
const int MAX = 3e5 + 5;
pii dir[4] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n = 0;
int comp = 0;
int par[MAX];
int get(int node){
if(par[node] < 0) return node;
return par[node] = get(par[node]);
}
bool unite(int v, int u){
v = get(v);
u = get(u);
if(v == u) return false;
if(-par[v] < -par[u]) swap(v, u);
par[v] += par[u];
par[u] = v;
comp--;
return true;
}
map<pii, int> f;
int construct_roads(vector<int> x, vector<int> y) {
memset(par, -1, sizeof(par));
n = x.size();
comp = n;
for (int i = 0; i < n; i++)
{
f[{x[i], y[i]}] = i;
}
map<pii, int> roads;
vector<int> v, u;
for (int i = 0; i < n && comp > 1; i++)
{
for(pii d:dir){
pii p = {x[i] + d.first * 2, y[i] + d.second * 2};
if(f.count(p)){
int idx = f[p];
if(unite(i, idx)){
v.push_back(i);
u.push_back(idx);
roads[{x[i] + d.first, y[i] + d.second}] = v.size() - 1;
}
}
}
}
if(comp != 1){
return 0;
}
map<pii, int> mp;
vector<pii> abc;
for(auto& p:roads){
for(pii d:dir){
pii b = {p.first.first + d.first, p.first.second + d.second};
if(f.count(b)) continue;
mp[b]++;
}
}
for(auto& p:mp){
if(p.second == 1) {
abc.push_back(p.first);
roads.erase(p.first);
}
}
vector<int> a(n - 1), b(n - 1);
while(abc.size()){
pii p = abc.back();
abc.pop_back();
if(mp[p] == 0) continue;
mp[p]--;
for(pii d:dir){
pii c = {p.first + d.first, p.second + d.second};
if(roads.count(c)){
int idx = roads[c];
a[idx] = p.first;
b[idx] = p.second;
roads.erase(c);
c.first += d.first;
c.second += d.second;
mp[c] -= 1;
if(mp[c] == 1){
abc.push_back(c);
}
break;
}
}
}
for(auto& p:mp){
if(p.second <= 0) continue;
for(pii d:dir){
pii c = {p.first.first + d.first, p.first.first + d.second};
if(roads.count(c)){
int idx = roads[c];
a[idx] = p.first.first;
b[idx] = p.first.second;
roads.erase(c);
break;
}
}
}
build(u, v, a, b);
return 1;
}
