#include "bits/stdc++.h"
#include "parks.h"
using namespace std;
vector<pair<int, int>> points(pair<int, int> A, pair<int, int> B)
{
if (A.first == B.first)
return {{A.first + 1, (A.second + B.second) / 2}, {A.first - 1, (A.second + B.second) / 2}};
return {{(A.first + B.first) / 2, B.second + 1}, {(A.first + B.first) / 2, B.second - 1}};
}
int construct_roads(vector<int> x, vector<int> y)
{
int n = x.size();
if (n == 1)
{
build({}, {}, {}, {});
return 1;
}
vector<int> u, v, a(n), b(n), vis(n);
map<pair<int, int>, int> mp, pick;
vector<vector<int>> g(n);
for (int i = 0; i < n; i++)
mp[{x[i], y[i]}] = i;
auto dfs = [&](auto dfs, int x, int y) -> void
{
vis[mp[{x, y}]] = 1;
if (mp.count({x + 2, y}) && !vis[mp[{x + 2, y}]])
dfs(dfs, x + 2, y), g[mp[{x, y}]].push_back(mp[{x + 2, y}]);
if (mp.count({x, y + 2}) && !vis[mp[{x, y + 2}]])
dfs(dfs, x, y + 2), g[mp[{x, y}]].push_back(mp[{x, y + 2}]);
if (mp.count({x - 2, y}) && !vis[mp[{x - 2, y}]])
dfs(dfs, x - 2, y), g[mp[{x, y}]].push_back(mp[{x - 2, y}]);
if (mp.count({x, y - 2}) && !vis[mp[{x, y - 2}]])
dfs(dfs, x, y - 2), g[mp[{x, y}]].push_back(mp[{x, y - 2}]);
};
dfs(dfs, x[0], y[0]);
for (auto &i : vis)
if (i == 0)
return 0;
vector<int> bad(n);
auto change = [&](auto &&change, int i) -> void
{
vector<pair<int, int>> pts = points({x[u[i]], y[u[i]]}, {x[v[i]], y[v[i]]});
for (auto &[x, y] : pts)
{
if (!pick.count({x, y}))
pick[{x, y}] = i, a[i] = x, b[i] = y;
return;
}
for (auto &[x, y] : pts)
{
if (!bad[pick[{x, y}]])
{
bad[pick[{x, y}]] = 1;
change(change, pick[{x, y}]);
pick[{x, y}] = i, a[i] = x, b[i] = y;
bad[pick[{x, y}]] = 0;
return;
}
}
};
int z = 0;
for (int i = 0; i < n; i++)
for (auto &j : g[i])
{
u.push_back(i);
v.push_back(j);
bad[z] = 1;
change(change, z);
bad[z] = 0;
z++;
}
build(u, v, a, b);
return 1;
}
