#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/hp/contests/debug.h"
#else
#define debug(...) void(37)
#endif
struct DSU {
vector<int> link;
DSU(int n) {
link.resize(n);
iota(link.begin(), link.end(), 0);
}
int get(int v) {
return link[v] = (link[v] == v ? v : get(link[v]));
}
bool unite(int x, int y) {
x = get(x), y = get(y);
if (x == y) return false;
link[y] = x;
return true;
}
};
int construct_roads(std::vector<int> X, std::vector<int> Y) {
debug(X, Y);
int N = int(X.size());
map<array<int, 2>, int> id;
for (int i = 0; i < N; ++i) {
id[{X[i], Y[i]}] = i;
}
auto Get = [&](int x, int y) {
if (id.count({x, y}) == 0) return -1;
return id[{x, y}];
};
vector<array<int, 2>> positions;
constexpr int dx[] = {-1, -1, +1, +1}, dy[] = {-1, +1, +1, -1};
for (int i = 0; i < N; ++i) {
for (int d = 0; d < 4; ++d) {
positions.push_back({X[i] + dx[d], Y[i] + dy[d]});
}
}
DSU comp(N);
sort(positions.begin(), positions.end());
positions.erase(unique(positions.begin(), positions.end()), positions.end());
vector<int> U, V, A, B;
for (auto[x, y] : positions) {
int parity = (x + y) / 2 % 2;
vector<int> take;
if (parity) {
take = {0, 2};
} else {
take = {1, 3};
}
debug(x, y, take);
for (auto t : take) {
int f = Get(x + dx[t], y + dy[t]);
int s = Get(x + dx[(t + 1) % 4], y + dy[(t + 1) % 4]);
debug(s, f);
if (min(f, s) > -1 && comp.unite(f, s)) {
U.push_back(f);
V.push_back(s);
A.push_back(x);
B.push_back(y);
break;
}
}
}
bool good = true;
for (int i = 0; i < N; ++i) {
good &= comp.get(i) == comp.get(0);
}
if (good) {
build(U, V, A, B);
return 1;
} else {
return 0;
}
}
