#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5;
int par[MAXN + 5];
vector<int> u, v, a, b;
map<pair<int, int>, int> mp;
map<pair<int, int>, bool> used;
int find(int idx){
return (par[idx] == idx ? idx : par[idx] = find(par[idx]));
}
void join(int A, int B, int X, int Y){
A = find(A), B = find(B);
if(A == B || used.count({X, Y})) return;
a.push_back(X), b.push_back(Y);
u.push_back(A), v.push_back(B);
par[B] = A;
used[{X, Y}] = 1;
}
int construct_roads(vector<int> x, vector<int> y) {
int N = x.size();
vector<pair<pair<int, int>, int>> coords;
for(int i = 0; i < N; i++){
coords.push_back({{x[i], y[i]}, i});
mp[{x[i], y[i]}] = i;
par[i] = i;
}
sort(coords.begin(), coords.end());
for(auto [i, j] : coords){
int parity = (i.first + i.second) % 4;
// kiri
if(mp.count({i.first, i.second - 2})){
join(j, mp[{i.first, i.second - 2}], i.first + (parity ? 1 : -1), i.second - 1);
}
// bawah
if(mp.count({i.first - 2, i.second})){
join(j, mp[{i.first - 2, i.second}], i.first - 1, i.second + (parity ? -1 : 1));
}
}
int cc = 0;
for(int i = 0; i < N; i++){
cc += (i == find(i));
}
if(cc > 1) return 0;
build(u, v, a, b);
return 1;
}
