#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef vector<ii> vi;
const int MAX_N=2e5+10;
vector<vi> ox(MAX_N),oy(MAX_N);
int pa[MAX_N],tam[MAX_N];
void init(int n){
for(int i=0;i<n;i++){
pa[i]=i; tam[i]=1;
}
}
int findset(int i){
if(pa[i]==i) return i;
return pa[i]=findset(pa[i]);
}
bool issameset(int i,int j){
return findset(i)==findset(j);
}
void unionset(int i,int j){
if(!issameset(i,j)){
int u=findset(i),v=findset(j);
pa[u]=v;
tam[v]+=tam[u];
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n=x.size();
for(int i=0;i<n;i++){
ox[x[i]].push_back(ii(y[i],i));
oy[y[i]].push_back(ii(x[i],i));
}
for(int i=0;i<MAX_N;i++){
sort(ox[i].begin(),ox[i].end());
sort(oy[i].begin(),oy[i].end());
}
vector<int> ru,rv,ra,rb;
set<ii> ba;
init(n);
for(int i=2;i<MAX_N;i+=2){
int t=oy[i].size();
for(int j=0;j<t-1;j++){
int xi=oy[i][j].first,xj=oy[i][j+1].first;
int u=oy[i][j].second,v=oy[i][j+1].second;
if(xj-xi==2 && !issameset(u,v)){
ru.push_back(oy[i][j].second);
rv.push_back(oy[i][j+1].second);
unionset(u,v);
int xk=oy[i][j+2].first;
auto it=lower_bound(oy[i-2].begin(),oy[i-2].end(),ii(xj,-1));
if(j+2<t && oy[i][j+2].first-xj==2 && it!=oy[i-2].end() && (*it).first==xj){
ra.push_back(xi+1); rb.push_back(i+1);
ba.insert(ii(xi+1,i+1));
it=lower_bound(oy[i+2].begin(),oy[i+2].end(),ii(xi,-1));
int id=it-oy[i+2].begin();
if(it!=oy[i+2].end() && (*it).first==xi && id-1>=0 && oy[i+2][id].first-oy[i+2][id-1].first==2){
int uu=oy[i+2][id].second,vv=oy[i+2][id-1].second;
unionset(uu,vv);
ru.push_back(uu); rv.push_back(vv);
ra.push_back(xi-1); rb.push_back(i+3);
}
}
else{
ra.push_back(xi+1); rb.push_back(i-1);
ba.insert(ii(xi+1,i-1));
}
}
}
}
for(int i=2;i<MAX_N;i+=2){
int t=ox[i].size();
for(int j=0;j<t-1;j++){
int yi=ox[i][j].first,yj=ox[i][j+1].first;
int u=ox[i][j].second,v=ox[i][j+1].second;
if(yj-yi==2){
ru.push_back(u); rv.push_back(v);
unionset(u,v);
if(ba.find(ii(i-1,yi+1))!=ba.end()){
ra.push_back(i+1); rb.push_back(yi+1);
ba.insert(ii(i+1,yi+1));
}
else{
ra.push_back(i-1); rb.push_back(yi+1);
ba.insert(ii(i-1,yi+1));
}
}
}
}
if(tam[findset(0)]!=n) return 0;
build(ru,rv,ra,rb);
return 1;
}
