#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
map<pair<int, int>, int> ctid;
set<pair<int, int>> bs;
vector<int> re1, re2, rbx, rby;
int par[MAXN], rnk[MAXN];
int root(int x){
if (par[x] == -1) return x;
else return par[x] = root(par[x]);
}
void join(int ra, int rb){
if (rnk[ra] > rnk[rb]) swap(ra, rb);
par[ra] = rb;
if (rnk[ra] == rnk[rb]) rnk[rb]++;
}
bool check(int bx, int by, int n0x, int n0y, int n1x, int n1y){
if (!ctid.count({n0x, n0y}) || !ctid.count({n1x, n1y})) return 0;
int n0id = ctid[{n0x, n0y}], n1id = ctid[{n1x, n1y}];
int r0 = root(n0id), r1 = root(n1id);
if (r0 == r1) return 0;
join(r0, r1);
re1.push_back(n0id); re2.push_back(n1id); rbx.push_back(bx); rby.push_back(by);
return 1;
}
int construct_roads(vector<int> xv, vector<int> yv) {
memset(par, -1, sizeof(par));
int nodes = xv.size();
for (int i = 0; i < nodes; i++) ctid[{xv[i], yv[i]}] = i;
for (auto &[loc, id] : ctid){
auto &[x, y] = loc;
if (ctid.count({x, y + 2})){
bs.insert({x - 1, y + 1}); bs.insert({x + 1, y + 1});
}
if (ctid.count({x + 2, y})){
bs.insert({x + 1, y - 1}); bs.insert({x + 1, y + 1});
}
}
for (auto &[bx, by] : bs){
int n0x, n0y, n1x, n1y;
if ((bx + by) % 4 == 0){
n0x = bx - 1; n1x = bx + 1; n0y = n1y = by - 1;
if (check(bx, by, n0x, n0y, n1x, n1y)) continue;
n0y = n1y = by + 1;
check(bx, by, n0x, n0y, n1x, n1y);
}
else{
n0x = n1x = bx - 1; n0y = by - 1; n1y = by + 1;
if (check(bx, by, n0x, n0y, n1x, n1y)) continue;
n0x = n1x = bx + 1;
check(bx, by, n0x, n0y, n1x, n1y);
}
}
if (re1.size() != nodes - 1) return 0;
build(re1, re2, rbx, rby);
return 1;
}
