#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define MP make_pair
#define all(x) (x).begin(), (x).end()
struct dsu {
vector<int> p, sz;
dsu(int n) {
p.assign(n, 0);
sz.assign(n, 1);
iota(p.begin(), p.end(), 0);
}
int find(int x) {
return (x == p[x] ? x : p[x] = find(p[x]));
}
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (sz[x] > sz[y]) swap(x, y);
p[x] = y;
sz[y] += sz[x];
return true;
}
};
int construct_roads(vector<int> x, vector<int> y) {
int n = (int)x.size();
if (n == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int, int>, int> id;
set<pair<int, int>> benches;
for (int i = 0; i < n; i++){
id[MP(x[i], y[i])] = i;
benches.insert(MP(x[i] - 1, y[i] - 1));
benches.insert(MP(x[i] - 1, y[i] + 1));
benches.insert(MP(x[i] + 1, y[i] - 1));
benches.insert(MP(x[i] + 1, y[i] + 1));
}
vector<int> U, V, A, B;
dsu d(n);
for (pair<int, int> bench : benches){
int a = bench.first, b = bench.second;
int par = ((a - 1) / 2 + (b - 1) / 2) % 2;
// cerr << a << ' ' << b << ' ' << par << endl;
if (par){ // down, up
int i = -1, j = -1;
if (id.find(MP(a - 1, b - 1)) != id.end()) i = id[MP(a - 1, b - 1)];
if (id.find(MP(a + 1, b - 1)) != id.end()) j = id[MP(a + 1, b - 1)];
if (i != -1 && j != -1 && d.unite(i, j)){
U.push_back(i);
V.push_back(j);
A.push_back(a);
B.push_back(b);
continue;
}
i = -1, j = -1;
if (id.find(MP(a - 1, b + 1)) != id.end()) i = id[MP(a - 1, b + 1)];
if (id.find(MP(a + 1, b + 1)) != id.end()) j = id[MP(a + 1, b + 1)];
if (i != -1 && j != -1 && d.unite(i, j)) {
U.push_back(i);
V.push_back(j);
A.push_back(a);
B.push_back(b);
continue;
}
} else { // left, right
int i = -1, j = -1;
if (id.find(MP(a - 1, b - 1)) != id.end()) i = id[MP(a - 1, b - 1)];
if (id.find(MP(a - 1, b + 1)) != id.end()) j = id[MP(a - 1, b + 1)];
if (i != -1 && j != -1 && d.unite(i, j)) {
U.push_back(i);
V.push_back(j);
A.push_back(a);
B.push_back(b);
continue;
}
i = -1, j = -1;
if (id.find(MP(a + 1, b - 1)) != id.end()) i = id[MP(a + 1, b - 1)];
if (id.find(MP(a + 1, b + 1)) != id.end()) j = id[MP(a + 1, b + 1)];
if (i != -1 && j != -1 && d.unite(i, j)) {
U.push_back(i);
V.push_back(j);
A.push_back(a);
B.push_back(b);
continue;
}
}
}
if ((int)U.size() == n - 1){
build(U, V, A, B);
return 1;
}
return 0;
}
