#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
const int maxn = 2e5+10;
int linha[] = {-2, 2, 0, 0};
int coluna[] = {0, 0, -2, 2};
struct Pt
{
int x, y, ind;
} a[maxn];
struct Road
{
int u, v, x, y;
} road[maxn];
bool mark[maxn];
struct DSU
{
int pai[maxn], peso[maxn];
void init(int n)
{
for (int i = 1; i <= n; i++)
pai[i] = i;
}
int Find(int x)
{
if (pai[x] == x) return x;
return pai[x] = Find(pai[x]);
}
void Join(int x, int y)
{
x = Find(x), y = Find(y);
if (x == y) return;
if (peso[x] < peso[y]) swap(x, y);
pai[y] = x, peso[x] += peso[y];
}
} dsu;
bool comp(Pt a, Pt b)
{
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int construct_roads(vector<int> X, vector<int> Y)
{
int n = X.size();
bool sub = 1;
int mn = 8, mx = 0;
map<pair<int, int>, int> mp;
for (int i = 1; i <= n; i++)
{
a[i] = {X[i-1], Y[i-1], i};
mp[{a[i].x, a[i].y}] = i;
mx = max(mx, a[i].x);
mn = min(mn, a[i].x);
}
if (mx > 6) sub = 0;
dsu.init(n);
if (sub)
{
map<pair<int, int>, int> bench;
sort(a+1, a+n+1, comp);
int ind = 0;
for (int i = 1; i < n; i++)
{
if (dsu.Find(a[i].ind) != dsu.Find(a[i+1].ind) && a[i].x == a[i+1].x && a[i].y+2 == a[i+1].y)
{
dsu.Join(a[i].ind, a[i+1].ind);
road[++ind] = {a[i].ind, a[i+1].ind, a[i].x-1, a[i].y+1};
if (a[i].x == mx)
{
road[ind].x = a[i].x+1, road[ind].y = a[i].y+1;
bench[{a[i].x+1, a[i].y+1}] = 1;
}
else if (a[i].x == mn)
{
bench[{a[i].x-1, a[i].y+1}] = 1;
}
else
{
if (bench[{a[i].x-1, a[i].y+1}] == 1)
{
road[ind].x = a[i].x+1, road[ind].y = a[i].y+1;
bench[{a[i].x+1, a[i].y+1}] = 1;
}
else
{
bench[{a[i].x-1, a[i].y+1}] = 1;
}
}
}
if (mp[{a[i].x+2, a[i].y}] && dsu.Find(a[i].ind) != dsu.Find(mp[{a[i].x+2, a[i].y}]))
{
dsu.Join(a[i].ind, mp[{a[i].x+2, a[i].y}]);
if (bench[{a[i].x+1, a[i].y-1}])
{
road[++ind] = {a[i].ind, mp[{a[i].x+2, a[i].y}], a[i].x+1, a[i].y+1};
bench[{a[i].x+1, a[i].y+1}] = 1;
}
else
{
road[++ind] = {a[i].ind, mp[{a[i].x+2, a[i].y}], a[i].x+1, a[i].y-1};
bench[{a[i].x+1, a[i].y-1}] = 1;
}
}
}
if (ind != n-1) return 0;
vector<int> U, V, A, B;
for (int i = 1; i < n; i++)
{
U.push_back(road[i].u-1), V.push_back(road[i].v-1);
A.push_back(road[i].x), B.push_back(road[i].y);
}
build(U, V, A, B);
return 1;
}
map<pair<int, int>, int> bench;
int ind = 0;
queue<int> fila;
fila.push(1), mark[1] = 1;
while (!fila.empty())
{
int i = fila.front(); fila.pop();
for (int j = 0; j < 4; j++)
{
int dx = a[i].x+linha[j], dy = a[i].y+coluna[j];
if (!mp[{dx, dy}]) continue;
int o = mp[{dx, dy}];
if (mark[o]) continue;
mark[o] = 1, fila.push(o);
if (dsu.Find(i) != dsu.Find(o) && a[i].x == a[o].x)
{
dsu.Join(i, o);
int mn = min(a[i].y, a[o].y);
road[++ind] = {i, o, a[i].x-1, mn+1};
if (bench[{a[i].x-1, mn+1}] == 1)
{
road[ind].x = a[i].x+1, road[ind].y = mn+1;
bench[{a[i].x+1, mn+1}] = 1;
}
else
{
bench[{a[i].x-1, mn+1}] = 1;
}
}
if (dsu.Find(i) != dsu.Find(o) && a[i].y == a[o].y)
{
dsu.Join(i, o);
int mn = min(a[i].x, a[o].x);
if (bench[{mn+1, a[i].y-1}])
{
road[++ind] = {i, o, mn+1, a[i].y+1};
bench[{mn+1, a[i].y+1}] = 1;
}
else
{
road[++ind] = {i, o, mn+1, a[i].y-1};
bench[{mn+1, a[i].y-1}] = 1;
}
}
}
}
if (ind != n-1) return 0;
vector<int> U, V, A, B;
for (int i = 1; i < n; i++)
{
U.push_back(road[i].u-1), V.push_back(road[i].v-1);
A.push_back(road[i].x), B.push_back(road[i].y);
}
build(U, V, A, B);
return 1;
}
