//Challenge: Accepted
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
vector<pii> xv[maxn], yv[maxn];
unordered_map<ll, vector<pii> > adj;
unordered_map<ll, bool> vis;
ll h(int x, int y) {
return (ll)x * maxn + y;
}
struct DSU{
int par[maxn];
int merges = 0;
void init(int n) {
for (int i = 0;i < n;i++) par[i] = i;
}
int find(int a) {
return a == par[a] ? a : (par[a] = find(par[a]));
}
void Union(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
merges++;
par[a] = b;
}
} dsu;
vector<int> u, v, a, b;
void dfs(ll n, ll prv) {
vis[n] = 1;
for (auto p:adj[n]) {
if (p.ff != prv) {
u.push_back(p.ss / maxn);
v.push_back(p.ss % maxn);
a.push_back(n / maxn);
b.push_back(n % maxn);
if (!vis[p.ff]) dfs(p.ff, n);
}
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
dsu.init(n);
for (int i = 0;i < n;i++) {
xv[x[i]].push_back({y[i], i});
yv[y[i]].push_back({x[i], i});
}
for (int i = 0;i < maxn;i += 2) {
sort(xv[i].begin(), xv[i].end());
sort(yv[i].begin(), yv[i].end());
for (int j = 0;j < (int)xv[i].size() - 1;j++) {
if (i == 4) continue;
if (xv[i][j].ff + 2 == xv[i][j+1].ff) {
dsu.Union(xv[i][j].ss, xv[i][j+1].ss);
u.push_back(xv[i][j].ss);
v.push_back(xv[i][j+1].ss);
b.push_back(xv[i][j].ff + 1);
if (i == 2) a.push_back(1);
else a.push_back(7);
}
}
for (int j = 0;j < (int)yv[i].size() - 1;j++) {
if (yv[i][j].ff + 2 == yv[i][j+1].ff) {
dsu.Union(yv[i][j].ss, yv[i][j+1].ss);
ll ind = h(yv[i][j].ss, yv[i][j+1].ss), v1 = h(yv[i][j].ff + 1, i-1), v2 = h(yv[i][j].ff + 1, i+1);
adj[v1].push_back({v2, ind});
adj[v2].push_back({v1, ind});
}
}
}
{
int i = 4;
for (int j = 0;j < (int)xv[i].size() - 1;j++) {
if (xv[i][j].ff + 2 == xv[i][j+1].ff) {
if (dsu.find(xv[i][j].ss) == dsu.find(xv[i][j+1].ss)) continue;
dsu.Union(xv[i][j].ss, xv[i][j+1].ss);
ll ind = h(xv[i][j].ss, xv[i][j+1].ss), v1 = h(i-1, xv[i][j].ff + 1), v2 = h(i+1, xv[i][j].ff + 1);
adj[v1].push_back({v2, ind});
adj[v2].push_back({v1, ind});
}
}
}
if (dsu.merges != n - 1) return 0;
for (auto i:adj) {
if (i.ss.size() == 1 && !vis[i.ff]) dfs(i.ff, -1);
}
for (auto i:adj) {
if (!vis[i.ff]) dfs(i.ff, i.ss[0].ff);
}
build(u, v, a, b);
return 1;
}
