#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);
auto vert = [&](pair<int, int> a) {
return x[a.first] == x[a.second];
};
sort(edges.begin(), edges.end(), [&](pair<int, int> a, pair<int, int> b) {
if (vert(a) != vert(b)) {
return vert(a) < vert(b);
}
if (vert(a)) {
return (x[a.first] != 4) < (x[b.first] != 4);
}
return min(x[a.first], x[a.second]) < min(x[b.first], x[b.second]);
});
set<pair<int, int>> benches;
auto add = [&](int aa, int bb) {
a.push_back(aa), b.push_back(bb);
benches.insert({aa, bb});
};
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 (y[u] == y[v]) {
if (x[u] == 2) {
add(x[u] + 1, y[u] + 1);
} else if (x[u] == 4) {
add(x[u] + 1, y[u] - 1);
} else {
while (true) {}
}
} else {
if (x[u] == 2) {
add(x[u] - 1, y[u] + 1);
} else if (x[u] == 6) {
add(x[u] + 1, y[u] + 1);
} else {
if (!benches.contains({x[u] + 1, y[u] + 1})) {
add(x[u] + 1, y[u] + 1);
} else if (!benches.contains({x[u] - 1, y[u] + 1})) {
add(x[u] - 1, y[u] + 1);
} else {
assert(false);
}
}
}
}
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
