#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
template <size_t N>
struct dsu
{
int64_t p[N];
dsu() { fill(p, p + N, -1); }
int64_t repr(int64_t u) { return p[u] < 0 ? u : p[u] = repr(p[u]); }
bool merge(int64_t i, int64_t j)
{
i = repr(i);
j = repr(j);
if (i == j)
return 0;
if (p[i] > p[j])
swap(i, j);
p[i] += p[j];
p[j] = i;
return 1;
}
bool same_set(int64_t i, int64_t j) { return repr(i) == repr(j); }
int64_t set_size(int64_t i) { return -p[repr(i)]; }
void reset() { fill(p.begin(), p.end(), -1); }
};
struct fountain
{
int x, y;
size_t i;
};
constexpr size_t N = 200000;
fountain f[N];
vector<pair<size_t, size_t>> edges;
dsu<N> d;
int construct_roads(vector<int> x, vector<int> y)
{
size_t n = x.size();
for (size_t i = 0; i < x.size(); ++i)
f[i].i = i, f[i].x = x[i], f[i].y = y[i];
sort(f, f + n, [](auto const &a, auto const &b)
{ return a.y == b.y ? a.x < b.x : a.y < b.y; });
for (size_t i = 0; i < n;)
{
size_t j = i;
while (j < n && f[j].y == f[i].y)
++j;
for (size_t k = i + 1; k < j; ++k)
if (f[k - 1].x + 2 == f[k].x)
if (d.merge(f[k - 1].i, f[k].i))
edges.emplace_back(f[k - 1].i, f[k].i);
if (f[j].y == f[i].y + 2)
{
size_t k = j;
while (i < j && k < n && f[k].y == f[j].y)
{
if (f[i].x < f[k].x)
++i;
else if (f[k].x < f[i].x)
++k;
else
{
if (d.merge(f[i].i, f[k].i))
edges.emplace_back(f[k].i, f[i].i);
++i;
++k;
}
}
}
i = j;
}
if (d.set_size(0) != n)
return 0;
vector<int> u, v, a, b;
for (auto const &[i, j] : edges)
{
u.push_back(i);
v.push_back(j);
if (x[i] == x[j])
{
b.push_back((y[i] + y[j]) >> 1);
if (((x[i] & 3) == 2) ^ ((min(y[i], y[j]) & 3) == 2))
a.push_back(x[i] - 1);
else
a.push_back(x[i] + 1);
}
else
{
a.push_back((x[i] + x[j]) >> 1);
if (((y[i] & 3) == 2) ^ ((min(x[i], x[j]) & 3) == 2))
b.push_back(y[i] + 1);
else
b.push_back(y[i] - 1);
}
}
build(u, v, a, b);
return 1;
}
