#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> x, y;
map<pair<int, int>, int> pos_idx;
map<pair<int, int>, int> edge_side;
set<pair<int, int>> vis;
set<pair<int, int>> bench_used;
vector<int> ret_u, ret_v, ret_a, ret_b;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
void dfs(int u) {
int xu = x[u], yu = y[u];
for (int i = 0; i < 4; i++) {
int xv = x[u] + 2*dx[i], yv = y[u] + 2*dy[i];
if (!pos_idx.count({xv, yv})) continue;
int v = pos_idx[{xv, yv}];
if (vis.count({u, v})) continue;
vis.insert({u, v});
if (vis.count({v, u})) {
dfs(v);
continue;
}
int bx, by;
if (dx[i] == 1) {
bx = xu + dx[i];
by = yu + 1;
} else if (dx[i] == -1) {
bx = xu + dx[i];
by = yu - 1;
} else if (dy[i] == 1) {
bx = xu - 1;
by = yu + dy[i];
} else if (dy[i] == -1) {
bx = xu + 1;
by = yu + dy[i];
}
if (!bench_used.count({bx, by})) {
ret_u.push_back(u);
ret_v.push_back(v);
ret_a.push_back(bx);
ret_b.push_back(by);
}
dfs(v);
}
}
int construct_roads(vector<int> _x, vector<int> _y) {
x = _x; y = _y;
int n = x.size();
for (int i = 0; i < n; i++) pos_idx[{x[i], y[i]}] = i;
dfs(0);
if (ret_u.size() < n-1) return 0;
build(ret_u, ret_v, ret_a, ret_b);
return 1;
}
