#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> e;
DSU (int n) {
e = vector<int>(n, -1);
}
int get(int x) {
return e[x] < 0 ? x : e[x] = get(e[x]);
}
int size(int x) {
return -e[get(x)];
}
bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x == y) return false;
if (e[x] > e[y]) swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
int N = x.size();
vector<map<int, int>> mp(N + 10);
for (int i = 0; i < N; ++i) {
mp[x[i]][y[i]] = i;
}
vector<map<int, int>> vis(N + 10);
DSU dsu(N);
vector<int> u, v, a, b;
for (int i = 0; i < N; ++i) {
if (mp[x[i]].count(y[i] + 2)) {
int j = mp[x[i]][y[i] + 2];
// cout << "x match:\n";
// cout << x[i] << " " << y[i] << "\n";
// cout << x[j] << " " << y[j] << "\n\n";
dsu.unite(i, j);
u.push_back(i);
v.push_back(j);
int ny = y[i] + 1;
int nx;
if (x[i] == 2) {
nx = 1;
} else if (x[i] == 6) {
nx = 7;
} else {
if ((y[i] / 2) % 2) {
nx = 5;
} else {
nx = 3;
}
}
a.push_back(nx);
b.push_back(ny);
vis[nx][ny] = 1;
}
}
for (int i = 0; i < N; ++i) {
if (mp[x[i] + 2].count(y[i])) {
int j = mp[x[i] + 2][y[i]];
if (dsu.unite(i, j)) {
// cout << x[i] << " " << y[i] << "\n";
// cout << x[j] << " " << y[j] << "\n\n";
u.push_back(i);
v.push_back(j);
int nx = x[i] + 1;
int ny = y[i] - 1;
if (vis[nx].count(ny)) ny = y[i] + 1;
assert(!vis[nx].count(ny));
a.push_back(nx);
b.push_back(ny);
vis[nx][ny] = 1;
}
}
}
// cout << dsu.size(0) << "\n";
if (dsu.size(0) != N) return 0;
build(u, v, a, b);
return 1;
}
