#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define all(x) begin(x), end(x)
#define sz(x) int(x.size())
#define pb push_back
using vi = vector<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
struct DSU {
vi p;
DSU(int n) : p(n, -1) {}
int find(int x) {
if (p[x] < 0) return x;
return p[x] = find(p[x]);
}
bool unite(int x, int y) {
x = find(x), y = find(y);
if (x == y) return false;
if (p[x] > p[y]) swap(x, y);
p[x] += p[y], p[y] = x;
return true;
}
};
int construct_roads(vi x, vi y) {
const int n = sz(x);
map<ii, int> id;
vii points(n);
forn(i, n) {
ii p = {x[i], y[i]};
id[p] = i;
points[i] = p;
}
sort(all(points));
vi ret_u, ret_v, ret_a, ret_b;
set<ii> used;
DSU dsu(n);
auto add = [&](int u, int v, int a, int b) {
if (!used.count({a, b}) && dsu.unite(u, v)) {
used.emplace(a, b);
ret_u.pb(u + 1), ret_v.pb(v + 1), ret_a.pb(a), ret_b.pb(b);
}
};
for (auto [x, y] : points) {
int parity = ((x + y) / 2) % 2;
if (id.count({x, y - 2})) {
add(id[{x, y}], id[{x, y - 2}], x + (parity ? 1 : -1), y - 1);
}
if (id.count({x - 2, y})) {
add(id[{x, y}], id[{x - 2, y}], x - 1, y + (parity ? -1 : 1));
}
}
int comps = 0;
forn(u, n) comps += dsu.find(u) == u;
if (comps > 1) return 0;
build(ret_u, ret_v, ret_a, ret_b);
return 1;
}
