#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int p[N];
int sz[N];
vector<pair<int, int>> inY[N];
int get(int v) {
return p[v] = (p[v] == v ? v : get(p[v]));
}
void unite(int u, int v) {
u = get(u);
v = get(v);
if (sz[u] > sz[v]) swap(u, v);
p[u] = v;
sz[v] += sz[u];
}
int construct_roads(vector<int> vx, vector<int> vy) {
int n = (int) vx.size();
map<pair<int, int>, int> mp;
for (int i = 0; i < n; ++i) {
p[i] = i;
sz[i] = 1;
mp[{vx[i], vy[i]}] = i;
inY[vy[i]].emplace_back(vx[i], i);
}
for (int y = 2; y < N; y += 2) {
sort(inY[y].begin(), inY[y].end());
}
set<pair<int, int>> se;
vector<int> u, v, a, b;
for (int y = 2; y < N; y += 2) {
for (auto [x, i] : inY[y]) {
if (mp.count({x + 2, y})) {
int id = mp[{x + 2, y}];
if (get(id) != get(i)) {
unite(i, id);
u.push_back(i);
v.push_back(id);
if (!se.count({x + 1, y - 1})) {
se.insert({x + 1, y - 1});
a.push_back(x + 1);
b.push_back(y - 1);
} else {
assert(!se.count({x + 1, y + 1}));
se.insert({x + 1, y + 1});
a.push_back(x + 1);
b.push_back(y + 1);
}
}
}
if (mp.count({x, y + 2})) {
int id = mp[{x, y + 2}];
if (get(id) != get(i)) {
unite(i, id);
u.push_back(i);
v.push_back(id);
if (!se.count({x - 1, y + 1})) {
se.insert({x - 1, y + 1});
a.push_back(x - 1);
b.push_back(y + 1);
} else {
assert(!se.count({x + 1, y + 1}));
se.insert({x + 1, y + 1});
a.push_back(x + 1);
b.push_back(y + 1);
}
}
}
}
}
if (sz[get(0)] != n) {
return 0;
}
build(u, v, a, b);
return 1;
}
