#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
int n;
map<pii, int> field;
vector<int> x, y, used;
vector<pii> e;
void dfs(int v, int p) {
if (used[v])
return;
if (p != -1)
e.emplace_back(v, p);
used[v] = 1;
int vx = x[v], vy = y[v];
pii t[4] = {{vx + 2, vy}, {vx - 2, vy}, {vx, vy + 2}, {vx, vy - 2}};
for (int i = 0; i < 4; i++)
if (field.count(t[i]))
dfs(field[t[i]], v);
}
int construct_roads(std::vector<int> X, std::vector<int> Y) {
n = X.size(), x = X, y = Y;
for (int i = 0; i < n; i++)
field[{x[i], y[i]}] = i;
used.resize(n, 0);
dfs(0, -1);
if (count(used.begin(), used.end(), 0))
return 0;
vector<int> us, vs;
set<pii> loc;
for (int i = 0; i < e.size(); i++) {
us.push_back(e[i].first), vs.push_back(e[i].second);
pii p = e[i];
pii mid = {(x[p.first] + x[p.second]) / 2, (y[p.first] + y[p.second]) / 2};
field[mid] = i;
if (x[p.first] == x[p.second]) {
loc.insert({mid.first-1, mid.second});
loc.insert({mid.first+1, mid.second});
} else {
loc.insert({mid.first, mid.second+1});
loc.insert({mid.first, mid.second-1});
}
}
vector<int> a(e.size(), -1), b(e.size());
if (*max_element(x.begin(), x.end()) <= 4) {
for (pii p : loc) {
if (p.first == 1) {
pii p1 = p;
p1.first++;
if (field.count(p1)) {
a[field[p1]] = p.first, b[field[p1]] = p.second;
field.erase(p1);
}
} else if (p.first == 5) {
pii p1 = p;
p1.first--;
if (field.count(p1)) {
a[field[p1]] = p.first, b[field[p1]] = p.second;
field.erase(p1);
}
} else {
pii p1 = p, p2 = p;
p1.second++, p2.second--;
if (field.count(p1)) {
a[field[p1]] = p.first, b[field[p1]] = p.second;
field.erase(p1);
} else if (field.count(p2)) {
a[field[p2]] = p.first, b[field[p2]] = p.second;
field.erase(p2);
}
}
}
} else
for (pii p : loc) {
pii p1 = p, p2 = p;
if ((p.first / 2 + p.second / 2) % 2)
p1.first++, p2.first--;
else
p1.second++, p2.second--;
if (field.count(p1)) {
a[field[p1]] = p.first, b[field[p1]] = p.second;
field.erase(p1);
} else if (field.count(p2)) {
a[field[p2]] = p.first, b[field[p2]] = p.second;
field.erase(p2);
}
}
if (count(a.begin(), a.end(), -1))
return 0;
build(us, vs, a, b);
return 1;
}
