#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vii vector<vi>
#define pi pair<int,int>
#define vp vector<pi>
vi d;
vi h;
int parent(int x){
if(d[x]==x)return x;
return d[x]=parent(d[x]);
}
void connect(int a, int b){
a=parent(a);
b=parent(b);
if(h[a]<h[b])swap(a,b);
if(h[a]==h[b])h[a]++;
d[b]=a;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
//bsmllah
int n=x.size();
d.resize(n);for(int i=0;i<n;i++)d[i]=i;
h.resize(n);
vi u;
vi v;
vi a;
vi b;
map<pi,int>f;
for(int i=0;i<n;i++){
f.insert(make_pair(pi(x[i],y[i]),i));
}
vii k(4, vi(200001,-1));
for(int i=0;i<n;i++){
k[x[i]/2][y[i]]=i;
if(x[i]==4){
continue;
}
auto itr=f.find(pi(x[i],y[i]+2));
if(itr!=f.end()){
u.push_back(i);
v.push_back(itr->second);
a.push_back(x[i]+(x[i]>3?1:-1));
b.push_back(y[i]+1);
connect(i,itr->second);
}
}
if(k[2][2]!=-1){
if(k[1][2]!=-1){
u.push_back(k[1][2]);
v.push_back(k[2][2]);
connect(k[1][2],k[2][2]);
a.push_back(3);
b.push_back(1);
}
if(k[3][2]!=-1){
u.push_back(k[3][2]);
v.push_back(k[2][2]);
connect(k[3][2],k[2][2]);
a.push_back(5);
b.push_back(1);
}
}
for(int i=4;i<200001;i+=2){
if(k[2][i]==-1)continue;
if(k[2][i-2]==-1){
if(k[1][i]!=-1){
u.push_back(k[1][i]);
v.push_back(k[2][i]);
a.push_back(3);
b.push_back(i-1);
connect(k[1][i],k[2][i]);
}
if(k[3][i]!=-1){
u.push_back(k[3][i]);
v.push_back(k[2][i]);
a.push_back(5);
b.push_back(i-1);
connect(k[3][i],k[2][i]);
}
continue;
}
u.push_back(k[2][i]);
v.push_back(k[2][i-2]);
b.push_back(i-1);
if(i%4){
a.push_back(5);
}
else{
a.push_back(3);
}
connect(k[2][i],k[2][i-2]);
if(k[3][i-2]==-1 && k[3][i]!=-1){
u.push_back(k[3][i]);
v.push_back(k[2][i]);
a.push_back(5);
if(i%4){
b.push_back(i+1);
}
else {
b.push_back(i-1);
}
connect(k[3][i],k[2][i]);
}
if(k[1][i-2]==-1 && k[1][i]!=-1){
u.push_back(k[1][i]);
v.push_back(k[2][i]);
a.push_back(3);
if(i%4){
b.push_back(i-1);
}
else {
b.push_back(i+1);
}
connect(k[1][i],k[2][i]);
}
}
for(int i=0;i<n;i++){
if(parent(d[i])!=parent(d[0]))return 0;
}
build(u,v,a,b);
return 1;
}
