#include "parks.h"
#include <iostream>
#include <map>
#include <array>
#include <queue>
#define ll long long
using namespace std;
map <array<ll, 2>, ll> mp;
map <array<ll, 2>, ll> visited;
map <array<ll, 2>, ll> pt;
map <array<ll, 3>, ll> edge;
queue <array<ll, 2>> Q;
vector <int> U, V, A, B;
ll dj[4][2] = {-1, -1, -1, 1, 1, 1, 1, -1}, dk[4][2] = {-2, 0, 0, 2, 2, 0, 0, -2};
void dfs(ll u, ll v) {
++visited[{u, v}];
for (int i=0; i<4; ++i) {
ll nx = u + dk[i][0], ny = v + dk[i][1];
if (pt.count({nx, ny}) && !visited.count({nx, ny})) dfs(nx, ny);
}
}
void solve(ll u, ll v) {
for (int i=0; i<4; ++i) {
if (edge.count({u, v, i})) {
if (visited.count({u, v})) break;
++visited[{u, v}];
U.push_back(pt[{u + dj[i][0], v + dj[i][1]}]);
V.push_back(pt[{u + dj[(i+1)%4][0], v + dj[(i+1)%4][1]}]);
A.push_back(u);
B.push_back(v);
edge.erase({u, v, i});
edge.erase({u + dk[i][0], v + dk[i][1], i ^ 2});
solve(u + dk[i][0], v + dk[i][1]);
break;
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
ll n = x.size();
for (int i=0; i<n; ++i) {
pt[{x[i], y[i]}] = i;
for (int j=0; j<4; ++j) {
ll nx = x[i] + dj[j][0], ny = y[i] + dj[j][1];
++mp[{nx, ny}];
}
}
dfs(x[0], y[0]);
if (visited.size() != pt.size()) return 0;
for (auto it = mp.begin(); it != mp.end();) {
auto nx = next(it);
auto [u, v] = it->first;
ll tot = 0;
for (int i=0; i<4; ++i) {
if (pt.count({u + dj[i][0], v + dj[i][1]}) && pt.count({u + dj[(i+1)%4][0], v + dj[(i+1)%4][1]})) {
++tot;
++edge[{u, v, i}];
}
}
mp[{u, v}] = tot;
if (tot == 0) mp.erase(it);
else if (tot == 1) Q.push({u, v});
it = nx;
}
while (!Q.empty()) {
auto [u, v] = Q.front();
Q.pop();
if (!mp.count({u, v})) continue;
for (int i=0; i<4; ++i) {
if (edge.count({u, v, i})) {
U.push_back(pt[{u + dj[i][0], v + dj[i][1]}]);
V.push_back(pt[{u + dj[(i+1)%4][0], v + dj[(i+1)%4][1]}]);
edge.erase({u, v, i});
edge.erase({u + dk[i][0], v + dk[i][1], i ^ 2});
--mp[{u + dk[i][0], v + dk[i][1]}];
if (mp[{u + dk[i][0], v + dk[i][1]}] == 1) Q.push({u + dk[i][0], v + dk[i][1]});
else if (mp[{u + dk[i][0], v + dk[i][1]}] == 0) mp.erase({u + dk[i][0], v + dk[i][1]});
}
}
mp.erase({u, v});
A.push_back(u);
B.push_back(v);
}
for (auto [y, z] : mp) {
auto [u, v] = y;
if (z == 4) Q.push({u, v});
}
ll s = 0;
for (auto [y, z] : mp) {
if (z == 4) ++s;
else if (z == 3) --s;
}
if (s > 0) return 0;
for (auto [y, z] : mp) {
auto [u, v] = y;
if (z == 4) {
for (int i=0; i<4; ++i) {
if (edge.count({u, v, i})) {
edge.erase({u, v, i});
edge.erase({u + dk[i][0], v + dk[i][1], i ^ 2});
--mp[{u, v}];
break;
}
}
}
}
visited.clear();
for (auto [y, z] : mp) {
auto [u, v] = y;
solve(u, v);
}
build(U, V, A, B);
return 1;
}
