#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 = 100'000;
ll n = sz(x);
vc<vc<ll>> grid(3, vc<ll>(N, -1));
for (ll i = 0; i < n; i++)
grid[x[i] / 2 - 1][y[i] / 2 - 1] = i;
init(n);
vc<ll> ru, rv, rx, ry;
for (ll j = 0; j < 3; j++)
for (ll i = 0; i + 1 < N; i++) {
ll u = grid[j][i], v = grid[j][i + 1];
if (u != -1 and v != -1 and find(u) != find(v)) {
onion(u, v);
ru.pub(u);
rv.pub(v);
if (j == 0)
rx.pub(1);
else if (j == 1 and i % 2 == 1)
rx.pub(3);
else if (j == 1)
rx.pub(5);
else
rx.pub(7);
ry.pub(y[u] + 1);
}
}
for (ll i = 0; i < N; i++) {
ll u = grid[0][i], v = grid[1][i];
if (u != -1 and v != -1 and find(u) != find(v)) {
onion(u, v);
ru.pub(u);
rv.pub(v);
rx.pub(3);
if (i % 2 == 0)
ry.pub(y[u] + 1);
else
ry.pub(y[u] - 1);
}
u = grid[1][i], v = grid[2][i];
if (u != -1 and v != -1 and find(u) != find(v)) {
onion(u, v);
ru.pub(u);
rv.pub(v);
rx.pub(5);
if (i % 2 == 1)
ry.pub(y[u] + 1);
else
ry.pub(y[u] - 1);
}
}
if (cnt > 1)
return 0;
build(ru, rv, rx, ry);
return 1;
}
