#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
// trans rights
#define ll long long
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x), end(x)
int n;
vector<int> u, v, a, b;
map<pair<int, int>, int> mp;
set<pair<int, int>> done;
vector<pair<int, int>> dirs = {{0, 2}, {2, 0}, {0, -2}, {-2, 0}};
vector<pair<int, int>> bloc[2] = {{{-1, 1}, {1, 1}, {1, -1}, {-1, -1}}, {{1, 1}, {1, -1}, {-1, -1}, {-1, 1}}};
void dfs(int x, int y, int ldir = 0) {
done.insert({x, y});
for (int i = 0; i < 4; i++) {
int ndir = (ldir + 3 + i) % 4;
int nx = x + dirs[ndir].f;
int ny = y + dirs[ndir].s;
if (mp.find({nx, ny}) == mp.end()) continue;
if (done.find({nx, ny}) != done.end()) continue;
int tx = x + bloc[0][ndir].f;
int ty = y + bloc[0][ndir].s;
if (done.find({tx, ty}) == done.end()) {
u.push_back(mp[{x, y}]);
v.push_back(mp[{nx, ny}]);
done.insert({tx, ty});
a.push_back(tx);
b.push_back(ty);
dfs(nx, ny, ndir);
continue;
}
tx = x + bloc[1][ndir].f;
ty = y + bloc[1][ndir].s;
if (done.find({tx, ty}) == done.end()) {
u.push_back(mp[{x, y}]);
v.push_back(mp[{nx, ny}]);
done.insert({tx, ty});
a.push_back(tx);
b.push_back(ty);
dfs(nx, ny, ndir);
}
}
}
int construct_roads(vector<int> xs, vector<int> ys) {
srand(6969);
n = xs.size();
for (int i = 0; i < n; i++) {
mp[{xs[i], ys[i]}] = i;
}
for (int tst = 0; tst < 7; tst++) {
dfs(xs[rand() % n], ys[rand() % n]);
if (u.size() == n - 1) {
build(u, v, a, b);
return 1;
}
done.clear();
u.clear();
v.clear();
a.clear();
b.clear();
}
return 0;
}
