#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll, ll> pll;
#define vc vector
#define st first
#define nd second
#define all(a) a.begin(), a.end()
#define sz(a) (ll)a.size()
#define pub push_back
#define pob pop_back
ll cnt;
vc<ll> par, rnk;
void init(ll n) {
cnt = n;
par.assign(n, -1);
rnk.assign(n, -1);
}
ll find(ll v) {
if (par[v] == -1)
return v;
par[v] = find(par[v]);
return par[v];
}
void onion(ll v, ll w) {
ll x = find(v);
ll y = find(w);
if (x == y)
return;
cnt--;
if (rnk[x] < rnk[y])
par[x] = y;
else if (rnk[y] < rnk[x])
par[y] = x;
else {
par[x] = y;
rnk[y]++;
}
}
ll construct_roads(std::vc<ll> x, std::vc<ll> y) {
ll n = sz(x);
ll N = 200'001;
vc<map<ll, ll>> c(N);
for (ll i = 0; i < n; i++)
c[x[i]][y[i]] = i;
init(n);
vc<ll> ru(n - 1), rv(n - 1), rx(n - 1), ry(n - 1);
ll j = 0;
for (ll u = 0; u < n; u++) {
vc<ll> ox = {2, 0};
vc<ll> oy = {0, 2};
for (ll i = 0; i < 2; i++) {
ll vx = x[u] + ox[i];
ll vy = y[u] + oy[i];
if (c[vx].find(vy) == c[vx].end())
continue;
ll v = c[vx][vy];
if (find(u) == find(v))
continue;
onion(u, v);
ru[j] = u;
rv[j] = v;
if (i == 0) {
rx[j] = vx - 1;
if ((vx + vy) / 2 % 2 == 1)
ry[j] = vy + 1;
else
ry[j] = vy - 1;
} else {
if ((vx + vy) / 2 % 2 == 0)
rx[j] = vx + 1;
else
rx[j] = vx - 1;
ry[j] = vy - 1;
}
j++;
}
}
if (j < n - 1)
return 0;
build(ru, rv, rx, ry);
return 1;
}
