#include "parks.h"
#include <iostream>
#include <map>
#include <array>
#define ll long long
using namespace std;
map <array<ll, 2>, ll> mp;
map <array<ll, 2>, array<ll, 2>> mp2;
vector <ll> adj[200000];
bool visited[200000];
ll dj[4][2] = {0, 2, 0, -2, 2, 0, -2, 0}, X[200000], Y[200000];
void dfs(ll u, ll dir) {
visited[u] = 1;
for (auto v : adj[u]) {
if (visited[v]) continue;
ll a = (X[u]+X[v])/2+(Y[v]-Y[u])/2 * dir;
ll b = (Y[u]+Y[v])/2+(X[u]-X[v])/2 * dir;
if (!mp2.count({a, b})) {
mp2[{a, b}] = {u, v};
dfs(v, -dir);
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
mp.clear();
mp2.clear();
for (int i=0; i<x.size(); ++i) {
X[i] = x[i], Y[i] = y[i];
visited[i] = 0;
adj[i].clear();
mp[{x[i], y[i]}] = i;
}
for (int i=0; i<x.size(); ++i) {
for (int j=0; j<4; ++j) {
ll nx = x[i] + dj[j][0], ny = y[i] + dj[j][1];
if (mp.count({nx, ny})) {
ll a = mp[{x[i], y[i]}];
ll b = mp[{nx, ny}];
adj[a].push_back(b);
adj[b].push_back(a);
}
}
}
dfs(0, 1);
vector <int> U, V, A, B;
if (mp2.size() != (ll)x.size()-1) return 0;
else {
auto it = mp2.begin();
while (it != mp2.end()) {
U.push_back(it->second[0]);
V.push_back(it->second[1]);
A.push_back(it->first[0]);
B.push_back(it->first[1]);
it = next(it);
}
build(U, V, A, B);
return 1;
}
}
