#include <bits/stdc++.h>
#include "parks.h"
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 1e18+5
#define eps 1e-7
#define eps1 1e-2
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
#define V 450
using namespace std;
const int MOD = 1e9+7;
const int nax = 2e5+5;
const int nax2 = 105;
vii srt1[nax], srt2[nax];
ve<pair<int,ii>> ysrt[nax];
int parent[nax];
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b)
parent[b] = a;
}
set<int> xs,ys;
map<ll, bool> vis;
int construct_roads(vi x, vi y) {
int n = x.size();
vi u,v,a,b;
for (int i = 0; i < n; ++i)
{
xs.insert(x[i]);
ys.insert(y[i]);
srt1[x[i]].pb({y[i], i});
srt2[y[i]].pb({x[i], i});
parent[i] = i;
}
for(auto cury : ys){
vii srt = srt2[cury];
sort(srt.begin(), srt.end());
for (int i = 0; i < srt.size()-1; ++i)
{
int curx = srt[i].fi;
if(srt[i+1].fi-srt[i].fi == 2)
ysrt[curx].pb({cury,{srt[i].se,srt[i+1].se}});
}
}
int cnt = 0;
for(auto curx : xs){
vii srt = srt1[curx];
sort(srt.begin(), srt.end());
for (int i = 0; i < (int)srt.size()-1; ++i)
{
if(srt[i+1].fi-srt[i].fi == 2){
if(find_set(srt[i].se) == find_set(srt[i+1].se)) continue;
u.pb(0), v.pb(0),a.pb(0),b.pb(0);
union_sets(srt[i].se,srt[i+1].se);
int ny = (srt[i].fi+srt[i+1].fi)/2;
u[cnt] = srt[i].se,v[cnt] = srt[i+1].se, b[cnt] = ny;
if(vis[ny*nax+curx-1]){
a[cnt] = curx+1;
vis[ny*nax+curx+1] = 1;
}
else{
vis[ny*nax+curx-1] = 1;
a[cnt] = curx-1;
}
cnt++;
}
}
for(auto cury : ysrt[curx]){
if(find_set(cury.se.fi) == find_set(cury.se.se)) continue;
u.pb(0), v.pb(0),a.pb(0),b.pb(0);
union_sets(cury.se.fi,cury.se.se);
u[cnt] = cury.se.fi,v[cnt] = cury.se.se;
a[cnt] = curx+1;
if(!vis[(cury.fi-1)*nax+curx+1]){
b[cnt] = cury.fi-1;
vis[(cury.fi-1)*nax+curx+1] = 1;
}
else{
b[cnt] = cury.fi+1;
vis[(cury.fi+1)*nax+curx+1] = 1;
}
cnt++;
}
}
int un = find_set(0);
for (int i = 1; i < n; ++i)
{
if(find_set(i) != un) return 0;
}
build(u,v,a,b);
return 1;
}
