#pragma GCC optimize("Ofast,unroll-loops")
#include "parks.h"
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
map<pii, int> id;
int n, m, deg[200000], dsu[200000], vis[400001], use[400001], hmm;
pii pos[400001];
vector<pair<pii, pii>> edge;
vector<pii> E[400001];
vector<int> ru, rv, bx, by;
int find(int k)
{
return dsu[k] == k ? k : dsu[k] = find(dsu[k]);
}
void merge(int x, int y)
{
x = find(x), y = find(y);
dsu[x] = y;
}
int node(int x, int y)
{
if (!id[pii(x, y)])
{
id[pii(x, y)] = ++m;
pos[m] = pii(x, y);
}
return id[pii(x, y)];
}
void dfs(int u, int p)
{
vis[u] = 1;
int flag = 1;
for (auto [v, i] : E[u])
if (!vis[v])
dfs(v, u);
hmm += E[u].size();
hmm -= 2;
for (auto [v, i] : E[u])
if (v != p && !use[i] && flag)
{
flag--;
use[i] = 1;
tie(bx[i], by[i]) = pos[u];
}
for (auto [v, i] : E[u])
if (!use[i] && flag)
{
flag--;
use[i] = 1;
tie(bx[i], by[i]) = pos[u];
}
}
int construct_roads(vector<int> x, vector<int> y)
{
for (int t = 0; t <= 4; t++)
n = x.size();
for (int i = 0; i < n; i++)
dsu[i] = i;
for (int i = 0; i < n; i++)
id[pii(x[i], y[i])] = i + 1;
bx.resize(n - 1), by.resize(n - 1);
for (int i = 0; i < n; i++)
{
if (id.find(pii(x[i], y[i] - 2)) != id.end())
{
int j = id[pii(x[i], y[i] - 2)] - 1;
merge(i, j);
ru.emplace_back(i);
rv.emplace_back(j);
}
if (id.find(pii(x[i] - 2, y[i])) != id.end())
{
int j = id[pii(x[i] - 2, y[i])] - 1;
edge.emplace_back(make_pair(pii(x[i] - 1, y[i]), pii(i, j)));
}
}
// sort(edge.begin(), edge.end(), [&](pair<pii, pii> f, pair<pii, pii> s)
// {
// pii p = f.F, q = s.F;
// if(p.F != q.F)
// return p.F < q.F;
// if(p.F % 4 == 1)
// return p.S < q.S;
// return p.S > q.S; });
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
shuffle(edge.begin(), edge.end(), rd);
for (auto [_, p] : edge)
{
auto [u, v] = p;
if (find(u) != find(v))
{
ru.emplace_back(u);
rv.emplace_back(v);
merge(u, v);
}
}
if (ru.size() < n - 1)
return 0;
id.clear();
for (int i = 0; i < n - 1; i++)
{
int u = ru[i], v = rv[i];
if (x[u] == x[v])
{
int a = node(x[u] - 1, (y[u] + y[v]) / 2),
b = node(x[u] + 1, (y[u] + y[v]) / 2);
E[a].emplace_back(pii(b, i));
E[b].emplace_back(pii(a, i));
}
else
{
int a = node((x[u] + x[v]) / 2, y[u] + 1),
b = node((x[u] + x[v]) / 2, y[u] - 1);
E[a].emplace_back(pii(b, i));
E[b].emplace_back(pii(a, i));
}
}
for (int i = 1; i <= m; i++)
if (!vis[i])
{
hmm = 0;
dfs(i, i);
if(hmm > 0)
return 0;
}
build(ru, rv, bx, by);
return 1;
}
