#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
const int maxn = 2e5+10;
struct Pt
{
int x, y, ind;
} a[maxn];
struct Road
{
int u, v, x, y;
} road[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;
}
}
