#include "parks.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
int n, cnt;
vector<int> f, sz;
DSU(int n) : n(n), cnt(n) {
f.resize(n);
iota(f.begin(), f.end(), 0);
sz.resize(n, 1);
}
int find(int u) {
if (f[u] == u) return u;
return f[u] = find(f[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
--cnt;
if (sz[v] > sz[u]) {
swap(u, v);
}
f[v] = u;
sz[u] += sz[v];
}
bool same(int u, int v) {
return find(u) == find(v);
}
};
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
int N = 2e5;
vector<map<int, int>> id(N + 1);
for (int i = 0; i < n; ++i) {
id[x[i]][y[i]] = i;
}
vector<map<int, int>> vis(N + 1);
DSU dsu(n);
vector<int> u, v, a, b;
for (int i = 0; i < n; ++i) {
if (id[x[i]].count(y[i] + 2)) {
int j = id[x[i]][y[i] + 2];
dsu.merge(i, j);
u.push_back(i);
v.push_back(j);
if (x[i] == 6) {
a.push_back(x[i] + 1);
b.push_back(y[i] + 1);
vis[x[i] + 1][y[i] + 1] = 1;
} else if (x[i] == 2) {
a.push_back(x[i] - 1);
b.push_back(y[i] + 1);
vis[x[i] - 1][y[i] + 1] = 1;
} else {
if ((y[i] / 2) % 2) {
a.push_back(x[i] + 1);
b.push_back(y[i] + 1);
vis[x[i] + 1][y[i] + 1] = 1;
} else {
a.push_back(x[i] - 1);
b.push_back(y[i] + 1);
vis[x[i] - 1][y[i] + 1] = 1;
}
}
}
}
for (int i = 0; i < n; ++i) {
if (x[i] == 4) {
if (id[x[i] + 2].count(y[i])) {
int j = id[x[i] + 2][y[i]];
if (dsu.same(i, j) == 0) {
u.push_back(i);
v.push_back(j);
dsu.merge(i, j);
if (vis[x[i] + 1][y[i] - 1] == 0) {
a.push_back(x[i] + 1);
b.push_back(y[i] - 1);
vis[x[i] + 1][y[i] - 1] = 1;
} else {
a.push_back(x[i] + 1);
b.push_back(y[i] + 1);
vis[x[i] + 1][y[i] + 1] = 1;
}
}
}
if (id[x[i] - 2].count(y[i])) {
int j = id[x[i] - 2][y[i]];
if (dsu.same(i, j) == 0) {
u.push_back(i);
v.push_back(j);
dsu.merge(i, j);
if (vis[x[i] - 1][y[i] - 1]) {
a.push_back(x[i] - 1);
b.push_back(y[i] - 1);
vis[x[i] - 1][y[i] - 1] = 1;
} else {
a.push_back(x[i] - 1);
b.push_back(y[i] + 1);
vis[x[i] - 1][y[i] + 1] = 1;
}
}
}
}
}
if (dsu.cnt == 1) {
build(u, v, a, b);
return 1;
}
return 0;
}
