#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> parent;
int find(int v) {
if (v == parent[v]) return v;
return parent[v] = find(parent[v]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
parent[a] = b;
}
map<pair<int, int>, int> mp;
int construct_roads(vector<int> X, vector<int> Y) {
int N = X.size();
for (int i = 0; i < N; ++i) {
mp[{X[i], Y[i]}] = i;
parent.push_back(i);
}
for (int i = 0; i < N; ++i) {
int x = X[i];
int y = Y[i];
if (mp.find({x, y + 2}) != mp.end()) unite(i, mp[{x, y + 2}]);
if (mp.find({x, y - 2}) != mp.end()) unite(i, mp[{x, y - 2}]);
if (mp.find({x - 2, y}) != mp.end()) unite(i, mp[{x - 2, y}]);
if (mp.find({x + 2, y}) != mp.end()) unite(i, mp[{x + 2, y}]);
}
for (int i = 0; i < N; ++i) if (find(i) != find(0)) return 0;
// assume X is 2, 4, or 6 first.
for (int i = 0; i < N; ++i) parent[i] = i;
vector<int> u;
vector<int> v;
vector<int> a;
vector<int> b;
bool side = false; // false = left, true = right
set<pair<int, int>> taken;
for (int i = 0; i < N; ++i) {
int x = X[i];
int y = Y[i];
if (mp.find({x, y - 2}) != mp.end()) {
int j = mp[{x, y - 2}];
unite(i, j);
int a_here;
if (x == 2) a_here = 1;
else if (x == 6) a_here = 7;
else {
a_here = side? 5: 3;
side = !side;
}
u.push_back(i);
v.push_back(j);
a.push_back(a_here);
b.push_back(y - 1);
taken.insert({a_here, y - 1});
}
}
for (int y = 200006; y >= 0; y -= 2) {
for (int x = 2; x <= 4; x += 2) {
if (mp.find({x, y}) != mp.end() && mp.find({x + 2, y}) != mp.end()) {
int i = mp[{x, y}];
int j = mp[{x + 2, y}];
if (find(i) == find(j)) continue;
unite(i, j);
u.push_back(i);
v.push_back(j);
int a_here, b_here;
if (taken.find({x + 1, y + 1}) != taken.end()) {
a_here = x + 1;
b_here = y - 1;
} else {
a_here = x + 1;
b_here = y + 1;
}
a.push_back(a_here);
b.push_back(b_here);
taken.insert({a_here, b_here});
}
}
}
build(u, v, a, b);
return 1;
}
