#include "parks.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7;
int dx[] = {0, 0, 2, -2}, dy[] = {2, -2, 0, 0};
int construct_roads(vi x, vi y) {
int n = SZ(x);
map<pi, int> mp;
for(int i = 0; i < n; i++)
mp[{x[i], y[i]}] = i;
V<pi> edges;
set<pi> vis;
function<void(int, int)> dfs = [&] (int X, int Y) {
vis.insert({X, Y});
for(int i = 0; i < 4; i++) {
int xx = X + dx[i], yy = Y + dy[i];
if(mp.count({xx, yy}) && !vis.count({xx, yy})) {
edges.EB(mp[{X, Y}], mp[{xx, yy}]);
dfs(xx, yy);
}
}
};
dfs(x[0], y[0]);
if(SZ(vis) != n) return 0;
vi u, v, a(n - 1), b(n - 1);
V<array<int, 3>> todo;
V<array<int, 3>> todo2;
set<pi> used;
for(int i = 0; i < n - 1; i++) {
u.PB(edges[i].F), v.PB(edges[i].S);
int X = (x[edges[i].F] + x[edges[i].S]) / 2;
int Y = (y[edges[i].F] + y[edges[i].S]) / 2;
if(x[edges[i].F] == x[edges[i].S]) { // vertical
if(X == 2) {
X--;
} else if(X == 6) {
X++;
} else {
todo.PB({i, X, Y});
continue;
}
} else { // horizontal
if(X == 3) {
Y++;
} else {
todo2.PB({i, X, Y});
continue;
}
}
a[i] = X, b[i] = Y;
used.insert({X, Y});
}
for(auto[i, X, Y]:todo) {
if(!used.count({X - 1, Y})) {
X--;
} else {
X++;
}
a[i] = X, b[i] = Y;
used.insert({X, Y});
}
for(auto[i, X, Y]:todo2) {
assert(!used.count({X, Y + 1}) || !used.count({X + 1, Y}));
if(!used.count({X, Y + 1})) {
Y++;
} else {
Y--;
}
a[i] = X, b[i] = Y;
used.insert({X, Y});
}
build(u, v, a, b);
return 1;
}
