#include "parks.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int par[N];
int find(int a){
if(a == par[a])return a;
return par[a] = find(par[a]);
}
bool merge(int a,int b){
a = find(a);
b = find(b);
if(a == b)
return 0;
par[a] = b;
return 1;
}
int construct_roads(vector<int> x, vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = x.size();
map<pair<int,int>,int> mp;
for(int i = 0;i<n;i++){
par[i] = i;
mp[{x[i],y[i]}] = i;
}
vector<int> u, v, a, b;
vector<pair<int,int>> ord;
for(int i = 0;i<n;i++){
for(auto dx:{-2,0,2}){
for(auto dy:{-2,0,2}){
if(abs(dx) + abs(dy) != 2)continue;
if(!mp.count({x[i]+dx,y[i]+dy}))continue;
if(merge(i,mp[{x[i]+dx,y[i]+dy}])){
ord.push_back({i,mp[{x[i]+dx,y[i]+dy}]});
//u.push_back(i);
//v.push_back(mp[{x[i]+dx,y[i]+dy}]);
}
}
}
}
sort(ord.begin(),ord.end(),[&](pair<int,int> c,pair<int,int> d){
if(max(x[c.first],x[c.second]) != max(x[d.first],x[d.second])){
return max(x[c.first],x[c.second]) < max(x[d.first],x[d.second]);
}
return max(y[c.first],y[c.second]) < max(y[d.first],y[d.second]);
});
for(auto c:ord){
u.push_back(c.first);
v.push_back(c.second);
}
if(u.size() != n-1)
return 0;
a.assign(n-1,-1);
b.assign(n-1,-1);
map<pair<int,int>,int> used;
map<int,int> cnt;
map<pair<int,int>,vector<int>> mpp;
set<pair<int,int>> s;
for(int i = 0;i<n-1;i++){
for(auto dx:{-1,1}){
for(auto dy:{-1,1}){
if(abs(x[u[i]]+dx - x[v[i]]) != 1 || abs(y[u[i]]+dy - y[v[i]]) != 1)continue;
cnt[i]++;
mpp[{x[u[i]]+dx,y[u[i]]+dy}].push_back(i);
}
}
s.insert({cnt[i],i});
}
while(s.size()){
auto tp = *s.begin();
if(tp.first == 0){
assert(0);
}
s.erase(tp);
int i = tp.second;
bool ok = 0;
for(auto dx:{-1,1}){
for(auto dy:{-1,1}){
if(ok)continue;
if(used.count({x[u[i]]+dx,y[u[i]]+dy}))continue;
if(abs(x[u[i]]+dx - x[v[i]]) != 1 || abs(y[u[i]]+dy - y[v[i]]) != 1)continue;
used[{x[u[i]]+dx,y[u[i]]+dy}] = 1;
a[i] = x[u[i]] + dx;
b[i] = y[u[i]] + dy;
for(auto z:mpp[{x[u[i]]+dx,y[u[i]]+dy}]){
if(a[z] != -1)continue;
s.erase({cnt[z],z});
cnt[z]--;
s.insert({cnt[z],z});
}
ok = 1;
}
}
}
build(u, v, a, b);
return 1;
}
