#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
bitset<200100> have[7];
int at[7][200100];
int construct1(int row) {
vector<int>u,v,x,y;
int prev = 0;
for(int i = 2; i <= 200000; i+=2) {
if(have[row][i]) {
if(prev) {
if(i-prev>2)
return 0;
u.push_back(at[row][i]);
v.push_back(at[row][i-2]);
x.push_back(row+1);
y.push_back(i-1);
}
prev = i;
}
}
build(u,v,x,y);
return 1;
}
int p[200100];
int abp(int n) {
if(p[n]==n) return n;
return p[n]=abp(p[n]);
}
int n;
int construct2(int row1, int row2) {
int prev1 = 0, prev2 = 0;
vector<pair<pair<int, int>, pair<int, int>>> edges;
for(int i = 2; i <= 200000; i+=2) {
if(have[row2][i]&&i>2){
if(have[row2][i-2])
edges.push_back({{at[row2][i], at[row2][i-2]}, {row2+1, i-1}});
}
if(have[row1][i]) {
if(i>2) {
if(have[row1][i-2])
edges.push_back({{at[row1][i], at[row1][i-2]}, {row1-1, i-1}});
}
if(have[row2][i])
edges.push_back({{at[row1][i], at[row2][i]}, {row1+1, i-1}});
}
}
iota(p,p+200100,0);
vector<int> u,v,x,y;
for(auto i: edges)
u.push_back(i.first.first), v.push_back(i.first.second),x.push_back(i.second.first),y.push_back(i.second.second);
int cnt = 0;
for(int i = 0; i < edges.size(); i++)
if(abp(u[i])!=abp(v[i]))
p[p[u[i]]]=p[v[i]],cnt++;
if(cnt!=n-1) return 0;
build(u,v,x,y);
return 1;
}
int construct_roads(vector<int> x, vector<int> y) {
n = x.size();
for(int i = 0; i < n; i++)
have[x[i]][y[i]] = 1,at[x[i]][y[i]]=i;
int a = have[2].count(), b = have[4].count(), c = have[6].count();
if(!a&&!b) return construct1(6);
if(!a&&!c) return construct1(4);
if(!c&&!b) return construct1(2);
if(!b) return 0;
if(!c) return construct2(2,4);
if(!a) return construct2(4,6);
return 1;
}
