#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;
map<pair<int,int>,int> used;
for(int i = 0;i<n-1;i++){
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.push_back(x[u[i]] + dx);
b.push_back(y[u[i]] + dy);
ok = 1;
}
}
}
build(u, v, a, b);
return 1;
}
