#include "parks.h"
#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 2e5 + 5;
int f[N], sz[N];
vector <ar <int, 2>> g[N];
int father(int x) {
if (f[x] != f[f[x]])
return f[x] = father(f[x]);
return f[x];
}
int dsu(int a, int b) {
a = father(a), b = father(b);
if (a == b)
return 0;
if (sz[a] < sz[b])
swap(a, b);
sz[a] += sz[b];
f[b] = a;
return 1;
}
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
vector <ar <int, 3>> a(n);
map <ar <int, 2>, int> mp;
int mn = 1e9, mx = 0;
for (int i = 0; i < n; i++)
sz[i] = 1, f[i] = i;
for (int i = 0; i < n; i++)
a[i] = {x[i], y[i], i}, mn = min(mn, x[i]), mx = max(mx, x[i]), g[x[i]].push_back({y[i], i}), mp[{a[i][0], a[i][1]}] = i;
sort(all(a));
vector <int> u, v, bx, by;
set <ar <int, 2>> tkn;
for (int i = mn; i <= mx; i += 2) {
sort(all(g[i]));
if (i == mn) {
for (int j = 1; j < g[i].size(); j++) {
int na = g[i][j - 1][1], nb = g[i][j][1];
if (y[nb] - y[na] == 2) {
int tmp = dsu(na, nb);
u.push_back(na);
v.push_back(nb);
bx.push_back(i - 1);
by.push_back(y[nb] - 1);
}
}
} else if (i == mx) {
for (int j = 1; j < g[i].size(); j++) {
int na = g[i][j - 1][1], nb = g[i][j][1];
if (y[nb] - y[na] == 2) {
int tmp = dsu(na, nb);
u.push_back(na);
v.push_back(nb);
bx.push_back(i + 1);
by.push_back(y[nb] - 1);
}
}
for (int j = 0; j < g[i].size(); j++) {
ar <int, 2> dream = {i - 2, g[i][j][0]};
if (mp.count(dream)) {
int k = mp[dream], nb = g[i][j][1];
if (dsu(k, g[i][j][1])) {
if (tkn.count({i - 1, y[nb] - 1})) {
u.push_back(k);
v.push_back(nb);
bx.push_back(i - 1);
by.push_back(y[nb] + 1);
tkn.insert({i - 1, y[nb] + 1});
} else {
u.push_back(k);
v.push_back(nb);
bx.push_back(i - 1);
by.push_back(y[nb] - 1);
tkn.insert({i - 1, y[nb] - 1});
}
}
}
}
} else {
for (int j = 1; j < g[i].size(); j++)
int tmp = dsu(g[i][j - 1][1], g[i][j][1]);
for (int j = 0; j < g[i].size(); j++) {
ar <int, 2> dream = {i - 2, g[i][j][0]};
if (mp.count(dream)) {
int k = mp[dream], nb = g[i][j][1];
if (dsu(k, g[i][j][1])) {
u.push_back(k);
v.push_back(nb);
bx.push_back(i - 1);
by.push_back(y[nb] - 1);
tkn.insert({i - 1, y[nb] - 1});
}
}
}
for (int j = 1; j < g[i].size(); j++) {
int na = g[i][j - 1][1], nb = g[i][j][1];
if (y[nb] - y[na] == 2) {
if (tkn.count({i - 1, y[nb] - 1})) {
u.push_back(na);
v.push_back(nb);
bx.push_back(i + 1);
by.push_back(y[nb] - 1);
tkn.insert({i + 1, y[nb] - 1});
} else {
u.push_back(na);
v.push_back(nb);
bx.push_back(i - 1);
by.push_back(y[nb] - 1);
tkn.insert({i - 1, y[nb] - 1});
}
}
}
}
}
int fa = father(0);
for (int i = 0; i < n; i++)
if (father(i) != fa)
return 0;
build(u, v, bx, by);
return 1;
}
