#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> p;
int find(int a){
if (a == p[a]) return p[a];
return p[a] = find(p[a]);
}
void merge(int a, int b){
a = find(a);
b = find(b);
p[b] = a;
}
int construct_roads(vector<int> x, vector<int> y){
int n = x.size();
map<int,vector<pair<int,int>>> rows, cols;
for (int i=0; i<n; i++){
rows[x[i]].push_back({y[i], i});
cols[y[i]].push_back({x[i], i});
}
vector<pair<int,int>> e;
for (auto [i, v] : rows){
sort(v.begin(), v.end());
for (int j=0; j+1<v.size(); j++){
if (v[j].first+2 == v[j+1].first) e.push_back({v[j].second, v[j+1].second});
}
}
for (auto [i, v] : cols){
sort(v.begin(), v.end());
for (int j=0; j+1<v.size(); j++){
if (v[j].first+2 == v[j+1].first) e.push_back({v[j].second, v[j+1].second});
}
}
p.resize(n);
for (int i=0; i<n; i++) p[i] = i;
vector<int> u, v, a, b;
for (auto [i, j] : e){
if (find(i) != find(j)){
u.push_back(i);
v.push_back(j);
if (x[i] == x[j]){
b.push_back((y[i]+y[j])/2);
if (x[i] == 2) a.push_back(1);
else a.push_back(5);
/*int rp = ((x[i]+1)/2+b.back()/2) % 2;
if (rp) a.push_back(x[i]+1);
else a.push_back(x[i]-1);*/
}
else {
a.push_back((x[i]+x[j])/2);
b.push_back(y[i]+1);
/*int up = ((y[i]+1)/2+a.back()/2) % 2;
if (up) b.push_back(y[i]-1);
else b.push_back(y[i]+1);*/
}
merge(i, j);
}
}
for (int i=0; i<n; i++){
if (find(i) != find(0)) return 0;
}
build(u, v, a, b);
return 1;
}
