#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
vector<vector<int> > g(maxn);
vector<int> sz(maxn, 0);
int dfs(int u)
{
sz[u] = 1;
for (int v : g[u]) if (!sz[v]) sz[u] += dfs(v);
return sz[u];
}
int construct_roads(vector<int> x, vector<int> y)
{
map<pair<int, int>, int> m;
int n = x.size();
for (int i = 0; i < n; i++)
m[{x[i], y[i]}] = i;
set<pair<int, int> > s;
for (int i = 0; i < n; i++)
{
if (m.count({x[i], y[i] + 2}))
{
int j = m[{x[i], y[i]+2}];
g[i].push_back(j), g[j].push_back(i);
s.insert({x[i]+1, y[i]+1}), s.insert({x[i]-1, y[i]+1});
}
if (m.count({x[i] + 2, y[i]}))
{
int j = m[{x[i]+2, y[i]}];
g[i].push_back(j), g[j].push_back(i);
s.insert({x[i]+1, y[i]+1}), s.insert({x[i]+1, y[i]-1});
}
}
vector<int> u, v, a, b;
if (dfs(0) != n) return 0;
for (pair<int, int> i : s)
{
int x = i.first, y = i.second;
bool updown = ((x^y)&2);
pair<int, int> p1, p2, q1, q2;
if (updown) // horizontalne ciary - y sa nemeni
{
p1 = {x-1, y-1}, p2 = {x+1, y-1};
q1 = {x-1, y+1}, q2 = {x+1, y+1};
}
else
{
p1 = {x-1, y-1}, p2 = {x-1, y+1};
q1 = {x+1, y-1}, q2 = {x+1, y+1};
}
if (m.count(p1) && m.count(p2))
u.push_back(m[p1]), v.push_back(m[p2]), a.push_back(x), b.push_back(y);
else if (m.count(q1) && m.count(q2))
u.push_back(m[q1]), v.push_back(m[q2]), a.push_back(x), b.push_back(y);
}
build(u, v, a, b);
return 1;
}
