#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int construct_roads(vector<int> x, vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int, int>, int> mp;
vector<int> u, v, a, b;
vector<pair<int, int>> e;
int n = (int)x.size();
for(int i = 0; i < n; i++){
if(mp.count({x[i], y[i] - 2})){
e.push_back({mp[{x[i], y[i] - 2}], i});
}
if(mp.count({x[i], y[i] + 2})){
e.push_back({mp[{x[i], y[i] + 2}], i});
}
if(mp.count({x[i] - 2, y[i]})){
e.push_back({mp[{x[i] - 2, y[i]}], i});
}
if(mp.count({x[i] + 2, y[i]})){
e.push_back({mp[{x[i] + 2, y[i]}], i});
}
mp[{x[i], y[i]}] = i;
}
vector<int> par(n, -1);
function<int(int)> getpar = [&](int x){
return (par[x] < 0 ? x : par[x] = getpar(par[x]));
};
auto mrg = [&](int x, int y){
x = getpar(x), y = getpar(y);
if(x == y)return false;
if(par[x] > par[y])swap(x, y);
par[x] += par[y], par[y] = x;
return true;
};
for(auto [i, j]: e){
if(mrg(i, j)){
u.push_back(i), v.push_back(j);
a.push_back((x[i] != x[j] ? 3 : (x[i] == 2 ? 1 : 5)));
b.push_back(max(y[i], y[j]) - 1);
}
}
int cnt = 0;
for(int i = 0; i < n; i++)cnt += par[i] < 0;
if(cnt > 1)return 0;
build(u, v, a, b);
return 1;
}
