#include <bits/stdc++.h>
using namespace std;
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
namespace {
class dsu {
int n;
vector<int> par;
public:
dsu(int n) : n(n), par(n) {
iota(par.begin(), par.end(), 0);
}
int root(int u) { return u == par[u] ? u : par[u] = root(par[u]); }
void merge(int u, int v) {
u = root(u), v = root(v);
if (u != v) {
par[v] = u;
}
}
};
} // namespace
int construct_roads(vector<int> x, vector<int> y) {
const int n = x.size();
vector<pair<pair<int, int>, int>> buf;
for (int i = 0; i < n; ++i) {
buf.push_back({{x[i], y[i]}, i});
}
sort(buf.begin(), buf.end());
auto contains = [&](int x, int y) {
pair<pair<int, int>, int> p = {{x, y}, -1};
auto it = lower_bound(buf.begin(), buf.end(), p);
return it != buf.end() && it->first == p.first;
};
auto compr = [&](int x, int y) {
pair<pair<int, int>, int> p = {{x, y}, -1};
return lower_bound(buf.begin(), buf.end(), p)->second;
};
vector<pair<int, int>> edges;
for (int i = 0; i < n; ++i) {
if (contains(x[i], y[i] + 2)) {
edges.push_back({i, compr(x[i], y[i] + 2)});
}
if (contains(x[i], y[i] - 2)) {
edges.push_back({i, compr(x[i], y[i] - 2)});
}
if (contains(x[i] + 2, y[i])) {
edges.push_back({i, compr(x[i] + 2, y[i])});
}
if (contains(x[i] - 2, y[i])) {
edges.push_back({i, compr(x[i] - 2, y[i])});
}
}
vector<int> uu, vv, a, b;
dsu dsu(n);
for (auto &[u, v] : edges) {
if (dsu.root(u) == dsu.root(v)) {
continue;
}
if (x[u] > x[v]) {
swap(u, v);
}
if (y[u] > y[v]) {
swap(u, v);
}
dsu.merge(u, v);
uu.push_back(u), vv.push_back(v);
if (x[u] == x[v] - 2) {
a.push_back(x[u] + 1), b.push_back(y[u] + 1);
} else {
if (x[u] == 2) {
a.push_back(x[u] - 1), b.push_back(y[u] + 1);
} else {
a.push_back(x[u] + 1), b.push_back(y[u] + 1);
}
}
}
int num = 0;
for (int i = 0; i < n; ++i) {
num += dsu.root(i) == dsu.root(0);
}
if (num != n) {
return 0;
}
build(uu, vv, a, b);
return 1;
}
#ifdef MACOS_LOCAL
#include "grader.cpp"
#endif
