#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;
}
}
};
class twosat {
int n;
vector<vector<int>> adj;
int id(int a, int nega) { return a + n * nega; }
public:
twosat(int n) : n(n), adj(2 * n) {}
void add_implication(int nega, int a, int negb, int b) {
adj[id(a, nega)].push_back(id(b, negb));
adj[id(b, !negb)].push_back(id(a, !nega));
}
vector<int> solve() {
vector<vector<int>> adjt(2 * n);
for (int i = 0; i < 2 * n; ++i) {
for (int &j : adj[i]) {
adjt[j].push_back(i);
}
}
vector<bool> vis(2 * n);
vector<int> stk;
auto dfs = [&](auto &&self, int u) {
if (vis[u]) {
return;
}
vis[u] = true;
for (int &i : adj[u]) {
self(self, i);
}
stk.push_back(u);
};
swap(adj, adjt);
for (int i = 0; i < 2 * n; ++i) {
dfs(dfs, i);
}
swap(adj, adjt);
auto post = stk;
reverse(post.begin(), post.end());
vis.assign(2 * n, false);
vector<int> root(2 * n);
vector<vector<int>> with_root(2 * n);
for (int &u : post) {
if (vis[u]) {
continue;
}
stk.clear();
dfs(dfs, u);
for (int &i : stk) {
root[i] = stk[0], with_root[stk[0]].push_back(i);
}
}
for (int i = 0; i < n; ++i) {
if (root[i] == root[i + n]) {
return {};
}
}
vis.assign(2 * n, false);
vector<int> topo(2 * n);
int idx = 0;
auto dfs2 = [&](auto &&self, int u) {
u = root[u];
if (vis[u]) {
return;
}
vis[u] = true;
for (int &uu : with_root[u]) {
for (int &i : adj[uu]) {
self(self, i);
}
}
topo[u] = idx++;
};
for (int i = 0; i < 2 * n; ++i) {
dfs2(dfs2, i);
}
vector<int> ans(n);
for (int i = 0; i < n; ++i) {
ans[i] = topo[root[i]] < topo[root[i + n]];
}
return ans;
}
};
} // 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];
};
vector<pair<int, int>> bridges, benches;
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);
bridges.push_back({u, v});
uu.push_back(u), vv.push_back(v);
if (vert({u, v})) {
benches.push_back({x[u] - 1, y[u]});
benches.push_back({x[u] + 1, y[u]});
} else {
benches.push_back({x[u], y[u] - 1});
benches.push_back({x[u], y[u] + 1});
}
}
sort(bridges.begin(), bridges.end());
sort(benches.begin(), benches.end());
bridges.erase(unique(bridges.begin(), bridges.end()), bridges.end());
benches.erase(unique(benches.begin(), benches.end()), benches.end());
auto bridge_exists = [&](pair<int, int> p) { return binary_search(bridges.begin(), bridges.end(), p); };
auto bridge_idx = [&](pair<int, int> p) { return int(lower_bound(bridges.begin(), bridges.end(), p) - bridges.begin()); };
auto bench_idx = [&](pair<int, int> p) { return int(lower_bound(benches.begin(), benches.end(), p) - benches.begin()); };
vector<pair<int, int>> bridge_bench;
for (int i = 0; i < int(uu.size()); ++i) {
int u = uu[i], v = vv[i];
if (vert({u, v})) {
bridge_bench.push_back({bridge_idx({u, v}), bench_idx({x[u] - 1, y[u]})});
bridge_bench.push_back({bridge_idx({u, v}), bench_idx({x[u] + 1, y[u]})});
} else {
bridge_bench.push_back({bridge_idx({u, v}), bench_idx({x[u], y[u] - 1})});
bridge_bench.push_back({bridge_idx({u, v}), bench_idx({x[u], y[u] + 1})});
}
}
sort(bridge_bench.begin(), bridge_bench.end());
bridge_bench.erase(unique(bridge_bench.begin(), bridge_bench.end()), bridge_bench.end());
auto idx = [&](pair<int, int> p) { return int(lower_bound(bridge_bench.begin(), bridge_bench.end(), p) - bridge_bench.begin()); };
twosat sat(bridge_bench.size());
for (int i = 0; i < int(uu.size()); ++i) {
int u = uu[i], v = vv[i];
if (vert({u, v})) {
sat.add_implication(1, idx({bridge_idx({u, v}), bench_idx({x[u] - 1, y[u]})}), 0, idx({bridge_idx({u, v}), bench_idx({x[u] + 1, y[u]})}));
sat.add_implication(0, idx({bridge_idx({u, v}), bench_idx({x[u] - 1, y[u]})}), 1, idx({bridge_idx({u, v}), bench_idx({x[u] + 1, y[u]})}));
} else {
sat.add_implication(1, idx({bridge_idx({u, v}), bench_idx({x[u], y[u] - 1})}), 0, idx({bridge_idx({u, v}), bench_idx({x[u], y[u] + 1})}));
sat.add_implication(0, idx({bridge_idx({u, v}), bench_idx({x[u], y[u] - 1})}), 1, idx({bridge_idx({u, v}), bench_idx({x[u], y[u] + 1})}));
}
}
auto add_if_bridge = [&](int x1, int y1, int x2, int y2, vector<pair<int, int>> &avoid) {
if (!contains(x1, y1) || !contains(x2, y2)) {
return;
}
int u = compr(x1, y1);
int v = compr(x2, y2);
if (u > v) {
swap(u, v);
}
if (bridge_exists({u, v})) {
avoid.push_back({u, v});
}
};
for (auto &[x, y] : benches) {
vector<pair<int, int>> avoid;
add_if_bridge(x - 1, y - 1, x - 1, y + 1, avoid);
add_if_bridge(x + 1, y - 1, x + 1, y + 1, avoid);
add_if_bridge(x - 1, y + 1, x + 1, y + 1, avoid);
add_if_bridge(x - 1, y - 1, x + 1, y - 1, avoid);
for (int i = 0; i < int(avoid.size()); ++i) {
for (int j = 0; j < i; ++j) {
sat.add_implication(0, idx({bridge_idx(avoid[i]), bench_idx({x, y})}), 1, idx({bridge_idx(avoid[j]), bench_idx({x, y})}));
}
}
}
int num = 0;
for (int i = 0; i < n; ++i) {
num += dsu.root(i) == dsu.root(0);
}
if (num != n) {
return 0;
}
auto ans = sat.solve();
vector<int> uans, vans, aans, bans;
for (int i = 0; i < int(ans.size()); ++i) {
if (!ans[i]) {
continue;
}
auto [bridx, benidx] = bridge_bench[i];
auto [u, v] = bridges[bridx];
auto [x, y] = benches[benidx];
uans.push_back(u), vans.push_back(v), aans.push_back(x), bans.push_back(y);
}
build(uans, vans, aans, bans);
return 1;
}
#ifdef MACOS_LOCAL
#include "grader.cpp"
#endif
