#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 20;
vector<int> adj[maxn];
bool flag[maxn];
map<pair<int, int>, int> evens;
int get(int x, int y) {
auto it = evens.find(make_pair(x, y));
if (it == evens.end()) {
return -1;
}
else {
return it->second;
}
}
void dfs(int u) {
flag[u] = true;
for (auto v: adj[u]) {
if (!flag[v]) {
dfs(v);
}
}
}
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
for (int i = 0; i < n; i++) {
evens[make_pair(x[i], y[i])] = i;
}
vector<pair<int, int>> roads;
set<pair<int, int>> odds;
for (int u = 0; u < n; u++) {
int v = get(x[u] + 2, y[u]);
if (v != -1) {
odds.emplace(x[u] + 1, y[u] - 1);
odds.emplace(x[u] + 1, y[u] + 1);
roads.emplace_back(u, v);
adj[u].push_back(v);
adj[v].push_back(u);
}
v = get(x[u], y[u] + 2);
if (v != -1) {
odds.emplace(x[u] - 1, y[u] + 1);
odds.emplace(x[u] + 1, y[u] + 1);
roads.emplace_back(u, v);
adj[u].push_back(v);
adj[v].push_back(u);
}
}
dfs(0);
for (int i = 0; i < n; i++) {
if (!flag[i]) {
return 0;
}
}
vector<int> _u, _v, _a, _b;
for (auto p: odds) {
int a = p.first;
int b = p.second;
int u = -1;
int v = -1;
if ((a + b) & 2) {
u = get(a - 1, b - 1);
v = get(a + 1, b - 1);
if (u != -1 && v != -1) {
_u.push_back(u);
_v.push_back(v);
_a.push_back(a);
_b.push_back(b);
}
else {
u = get(a - 1, b + 1);
v = get(a + 1, b + 1);
if (u != -1 && v != -1) {
_u.push_back(u);
_v.push_back(v);
_a.push_back(a);
_b.push_back(b);
}
}
}
else {
u = get(a - 1, b - 1);
v = get(a - 1, b + 1);
if (u != -1 && v != -1) {
_u.push_back(u);
_v.push_back(v);
_a.push_back(a);
_b.push_back(b);
}
else {
u = get(a + 1, b - 1);
v = get(a + 1, b + 1);
if (u != -1 && v != -1) {
_u.push_back(u);
_v.push_back(v);
_a.push_back(a);
_b.push_back(b);
}
}
}
}
build(_u, _v, _a, _b);
return 1;
}
