#include "parks.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
#define fr first
#define sc second
const int N=2e5+5;
vector<array<int,3>> g[N];
int p[N];
vector<int> sz(N,1);
int f(int x){
if(p[x]==x) return x;
return p[x]=f(p[x]);
}
bool add(int a, int b){
a=f(a);
b=f(b);
if(a==b) return 0;
if(rand()%2) swap(a,b);//<-может лагать
p[a]=b;
sz[b]+=sz[a];
return 1;
}
void add_edge(int a, int b, int u, int v){
g[a].pb({b,u,v});
g[b].pb({a,u,v});
}
int construct_roads(vector<int> x, vector<int> y) {
int n=x.size();
map<pair<int,int>,int> X,Y;
for(int i=0;i<n;i++){
p[i]=i;
X[{x[i],y[i]}]=i;
}
vector<int> u,v,a,b;
for(int i=0;i<n;i++){
if(X.count({x[i]-2,y[i]})){
int j=X[{x[i]-2,y[i]}];
if(add(i,j)){
u.pb(i);v.pb(j);
a.pb(-1);b.pb(-1);
int A=u.size()-1;
if(Y.count({x[i]-1,y[i]-1})){
int B=Y[{x[i]-1,y[i]-1}];
add_edge(A,B,x[i]-1,y[i]-1);
Y.erase({x[i]-1,y[i]-1});
}
else{
Y[{x[i]-1,y[i]-1}]=A;
}
if(Y.count({x[i]-1,y[i]+1})){
int B=Y[{x[i]-1,y[i]+1}];
add_edge(A,B,x[i]-1,y[i]+1);
Y.erase({x[i]-1,y[i]+1});
}
else{
Y[{x[i]-1,y[i]+1}]=A;
}
}
}
if(X.count({x[i],y[i]-2})){
int j=X[{x[i],y[i]-2}];
if(add(i,j)){
u.pb(i);v.pb(j);
a.pb(-1);b.pb(-1);
int A=u.size()-1;
if(Y.count({x[i]-1,y[i]-1})){
int B=Y[{x[i]-1,y[i]-1}];
add_edge(A,B,x[i]-1,y[i]-1);
Y.erase({x[i]-1,y[i]-1});
}
else{
Y[{x[i]-1,y[i]-1}]=A;
}
if(Y.count({x[i]+1,y[i]-1})){
int B=Y[{x[i]+1,y[i]-1}];
add_edge(A,B,x[i]+1,y[i]-1);
Y.erase({x[i]+1,y[i]-1});
}
else{
Y[{x[i]+1,y[i]-1}]=A;
}
}
}
}
if(sz[f(0)]<n) return 0;
int m=u.size();
vector<int> used(m);
function<void(int)> dfs=[&](int x){
used[x]=1;
for(auto [it,A,B]:g[x]){
if(used[it]) continue;
a[it]=A;
b[it]=B;
dfs(it);
}
};
for(auto [it,A]: Y){
if(used[A]) continue;
a[A]=it.fr;
b[A]=it.sc;
dfs(A);
}
for(int i=0;i<m;i++){
if(used[i]) continue;
a[i]=g[i].back()[1];
b[i]=g[i].back()[2];
g[i].pop_back();
dfs(i);
}
build(u,v,a,b);
return 1;
}
