#include<bits/stdc++.h>
#include "parks.h"
#define mk make_pair
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,PI,cc,dd;
pair <int, int> p[200009],P[1000009];
vector <pair <int, int> > X[200009],Y[200009];
vector <int> U,V,A,B;
bool bo[9][200009];
int fx[9][200009];
int msh[200009],zm[200009];
int fnd(int q){
if(msh[q]==0) return q; else return msh[q]=fnd(msh[q]);
}
void mrg(int q, int w){
q=fnd(q);w=fnd(w);if(q==w) return;if(zm[q]<zm[q]) swap(q,w);
msh[w]=q;if(zm[q]==zm[w]) zm[q]++;
}
bool check(){
set <int> st;
for(i=1; i<=PI; i++){
mrg(P[i].first,P[i].second);
}
for(i=1; i<=a; i++) st.insert(fnd(i));
if(st.size()==1) return 1; else return 0;
}
int construct_roads(std::vector<int> Xx, std::vector<int> Yy) {
a=Xx.size();
for(i=1; i<=a; i++){
p[i].first=Xx[i-1];p[i].second=Yy[i-1];
fx[p[i].first][p[i].second]=i;
}
for(i=1; i<=a; i++){
X[p[i].first].push_back(make_pair(p[i].second,i));
//Y[p[i].second].push_back(make_pair(p[i].first,i));
}
for(i=2; i<=6; i+=2){
sort(X[i].begin(),X[i].end());
if(i==4) continue;
e=X[i].size();
for(j=0; j<e-1; j++){
if(X[i][j].first+2<X[i][j+1].first) continue;
c=X[i][j].second;d=X[i][j+1].second;
U.push_back(c);V.push_back(d);
if(i==2){
A.push_back(i-1);B.push_back((p[c].second+p[d].second)/2);
}else{
A.push_back(i+1);B.push_back((p[c].second+p[d].second)/2);
}
}
}
i=4;e=X[i].size();cc=0;
for(j=0; j<e-1; j++){
if(X[i][j].first+2<X[i][j+1].first){
cc=0;
continue;
}
c=X[i][j].second;d=X[i][j+1].second;
U.push_back(c);V.push_back(d);
if(cc==0){
A.push_back(i+1);B.push_back((p[c].second+p[d].second)/2);
}else{
A.push_back(i-1);B.push_back((p[c].second+p[d].second)/2);
}
cc^=1;
}
for(i=0; i<A.size(); i++){
bo[A[i]][B[i]]=1;
}
for(j=2; j<=200000; j++){
if(fx[2][j]==0||fx[4][j]==0) continue;
if(bo[3][j-1]==0){
bo[3][j-1]=1;
U.push_back(fx[2][j]);V.push_back(fx[4][j]);
A.push_back(3);B.push_back(j-1);
continue;
}
if(bo[3][j+1]==0){
bo[3][j+1]=1;
U.push_back(fx[2][j]);V.push_back(fx[4][j]);
A.push_back(3);B.push_back(j+1);
continue;
}
}
for(j=2; j<=200000; j++){
if(fx[4][j]==0||fx[6][j]==0) continue;
if(bo[5][j-1]==0){
bo[5][j-1]=1;
U.push_back(fx[4][j]);V.push_back(fx[6][j]);
A.push_back(5);B.push_back(j-1);
continue;
}
if(bo[5][j+1]==0){
bo[5][j+1]=1;
U.push_back(fx[4][j]);V.push_back(fx[6][j]);
A.push_back(5);B.push_back(j+1);
continue;
}
}
/*cout<<U.size()<<endl;
for(i=0; i<U.size(); i++){
cout<<U[i]<<" "<<V[i]<<" "<<A[i]<<" "<<B[i]<<endl;
}*/
for(i=0; i<U.size(); i++){
PI++;P[PI].first=U[i];P[PI].second=V[i];
}
if(check()==0){
return 0;
}
for(i=0; i<U.size(); i++){
U[i]--;V[i]--;
}
build(U,V,A,B);
return 1;
}
