#include<bits/stdc++.h>
#include "parks.h"
using namespace std;
#define mp make_pair
#define pb push_back
vector<pair<int,int>> G;
vector<pair<int,int>> x_axis[200005];
vector<pair<int,int>> y_axis[200005];
vector<pair<int,int>> choose;
vector<int> u,v,a,b;
int Boss[200005];
int query(int node){
if(Boss[node]==node) return node;
return Boss[node]=query(Boss[node]);
}
int Union(int x,int y){
if(query(x)==query(y)) return 0;
Boss[query(x)]=query(y);
return 1;
}
int construct_roads(vector<int> x,vector<int> y){
for(int i=0;i<200005;i++){
Boss[i]=i;
}
for(int i=0;i<(int)x.size();i++){
x_axis[x[i]].pb(mp(y[i],i));
y_axis[y[i]].pb(mp(x[i],i));
}
for(int i=0;i<200005;i++){
sort(x_axis[i].begin(),x_axis[i].end());
sort(y_axis[i].begin(),y_axis[i].end());
}
//construct graph
for(int i=0;i<200005;i++){
for(int j=0;j<(int)x_axis[i].size()-1;j++){
//cout<<x_axis[i][j+1].first<<"\n";
if(x_axis[i][j+1].first-x_axis[i][j].first==2){
G.pb(mp(x_axis[i][j+1].second,x_axis[i][j].second));
}
}
for(int j=0;j<(int)y_axis[i].size()-1;j++){
if(y_axis[i][j+1].first-y_axis[i][j].first==2){
G.pb(mp(y_axis[i][j+1].second,y_axis[i][j].second));
}
}
}
for(auto i:G){
//cout<<i.first<<" "<<i.second<<"\n";
if(Union(i.first,i.second)){
choose.pb(mp(i.first,i.second));
}
}
for(auto i:choose){
//cout<<x[i.first]<<" "<<y[i.first]<<" "<<x[i.second]<<" "<<y[i.second]<<"\n";
if(x[i.first]==x[i.second] && x[i.first]==2){
u.pb(i.first);v.pb(i.second);a.pb(1);b.pb((y[i.first]+y[i.second])/2);
}
else if(x[i.first]==x[i.second] && x[i.first]==4){
u.pb(i.first);v.pb(i.second);a.pb(5);b.pb((y[i.first]+y[i.second])/2);
}
else{
u.pb(i.first);v.pb(i.second);a.pb(x[i.first]+1);b.pb(3);
}
//cout<<v.back()<<" \n";
}
//for(int i:v) cout<<i<<" ";
if((int)choose.size()==(int)x.size()-1){
build(u,v,a,b);
return 1;
}
return 0;
}
