#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
const int N = 200005;
int n;
vector<int> g[N];
bool c[N];
void dfs(int x)
{
c[x] = true;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (c[h])
continue;
dfs(h);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
std::vector<int> u, v, a, b;
n = sz(x);
vector<pair<int, int> > p;
map<pair<int, int>, int> mp;
for (int i = 0; i < n; ++i)
{
p.push_back(m_p(x[i], y[i]));
mp[m_p(x[i], y[i])] = i;
}
sort(all(p));
set<pair<int, int> > s;
for (int i = 0; i < n; ++i)
{
int x = p[i].fi;
int y = p[i].se;
if (mp.find(m_p(x + 2, y)) != mp.end())
{
u.push_back(mp[m_p(x, y)]);
v.push_back(mp[m_p(x + 2, y)]);
if (s.find(m_p(x + 1, y + 1)) == s.end())
{
a.push_back(x + 1);
b.push_back(y + 1);
}
else if (s.find(m_p(x + 1, y - 1)) == s.end())
{
a.push_back(x + 1);
b.push_back(y - 1);
}
else
{
assert(false);
}
s.insert(m_p(a.back(), b.back()));
g[u.back()].push_back(v.back());
g[v.back()].push_back(u.back());
}
if (mp.find(m_p(x, y + 2)) != mp.end())
{
u.push_back(mp[m_p(x, y)]);
v.push_back(mp[m_p(x, y + 2)]);
if (s.find(m_p(x + 1, y + 1)) == s.end())
{
a.push_back(x + 1);
b.push_back(y + 1);
}
else if (s.find(m_p(x - 1, y + 1)) == s.end())
{
a.push_back(x - 1);
b.push_back(y + 1);
}
else
{
assert(false);
}
s.insert(m_p(a.back(), b.back()));
g[u.back()].push_back(v.back());
g[v.back()].push_back(u.back());
}
}
dfs(0);
for (int i = 0; i < n; ++i)
{
if (!c[i])
return 0;
}
build(u, v, a, b);
return 1;
}
