#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
int f[200005];
int len[200005];
int ffather(int no){
if(f[no] == no){
return no;
}
return f[no] = ffather(f[no]);
}
bool joint(int u, int v){
u = ffather(u);
v = ffather(v);
if(u == v)return 1;
return 0;
}
void join(int u, int v){
u = ffather(u);
v = ffather(v);
if(len[u] < len[v]){
swap(u, v);
}
f[v] = u;
len[u] += len[v];
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
vector<pair<int, int>> two;
vector<pair<int, int>> four;
vector<pair<int, int>> six;
map<pair<int, int>, int> m;
for(int i = 0; i < (int)x.size(); ++i){
f[i] = i;
len[i] = 1;
m[{x[i], y[i]}] = i;
if(x[i] == 2){
two.push_back({y[i], i});
}else if(x[i] == 4){
four.push_back({y[i], i});
}else{
six.push_back({y[i], i});
}
}
sort(two.begin(), two.end());
sort(four.begin(), four.end());
sort(six.begin(), six.end());
vector<int> u, v, a, b;
for(int i = 0; i < (int)two.size()-1; ++i){
if(two[i].first == two[i+1].first - 2){
join(m[{2, two[i].first}], m[{2, two[i+1].first}]);
u.push_back(two[i].second);
v.push_back(two[i+1].second);
a.push_back(1);
b.push_back(two[i].first+1);
}
}
for(int i = 0; i < (int)six.size()-1; ++i){
//cout << "hi" << endl;
if(six[i].first == six[i+1].first - 2){
join(m[{6, six[i].first}], m[{6, six[i+1].first}]);
u.push_back(six[i].second);
v.push_back(six[i+1].second);
a.push_back(7);
b.push_back(six[i].first+1);
}
}
for(int i = 0; i < (int)four.size(); ++i){
if(i == (int)four.size()-1 || four[i].first != four[i+1].first-2){
if(m.count({2, four[i].first}) && !joint(m[{2, four[i].first}], m[{4, four[i].first}])){
join(m[{2, four[i].first}], m[{4, four[i].first}]);
u.push_back(four[i].second);
v.push_back(m[{2, four[i].first}]);
a.push_back(3);
b.push_back(four[i].first+1);
}
if(m.count({6, four[i].first}) && !joint(m[{6, four[i].first}], m[{4, four[i].first}])){
join(m[{6, four[i].first}], m[{4, four[i].first}]);
u.push_back(four[i].second);
v.push_back(m[{6, four[i].first}]);
a.push_back(5);
b.push_back(four[i].first+1);
}
continue;
}
//cout << four[i].second << endl;
if(m.count({2, four[i].first}) && m.count({6, four[i].first}) && !joint(m[{2, four[i].first}], m[{4, four[i].first}]) && !joint(m[{6, four[i].first}], m[{4, four[i].first}])){
join(m[{6, four[i].first}], m[{4, four[i].first}]);
join(m[{2, four[i].first}], m[{4, four[i].first}]);
join(m[{4, four[i].first}], m[{4, four[i+1].first}]);
u.push_back(four[i].second);
v.push_back(four[i+1].second);
a.push_back(3);
b.push_back(four[i].first+1);
u.push_back(four[i].second);
v.push_back(m[{2, four[i].first}]);
a.push_back(3);
b.push_back(four[i].first-1);
u.push_back(four[i].second);
v.push_back(m[{6, four[i].first}]);
a.push_back(5);
b.push_back(four[i].first+1);
}else if(m.count({2, four[i].first}) && !joint(m[{2, four[i].first}], m[{4, four[i].first}])){
join(m[{2, four[i].first}], m[{4, four[i].first}]);
join(m[{4, four[i].first}], m[{4, four[i+1].first}]);
u.push_back(four[i].second);
v.push_back(four[i+1].second);
a.push_back(5);
b.push_back(four[i].first+1);
u.push_back(four[i].second);
v.push_back(m[{2, four[i].first}]);
a.push_back(3);
b.push_back(four[i].first+1);
}else if(m.count({6, four[i].first}) && !joint(m[{6, four[i].first}], m[{4, four[i].first}])){
join(m[{6, four[i].first}], m[{4, four[i].first}]);
join(m[{4, four[i].first}], m[{4, four[i+1].first}]);
u.push_back(four[i].second);
v.push_back(four[i+1].second);
a.push_back(3);
b.push_back(four[i].first+1);
u.push_back(four[i].second);
v.push_back(m[{6, four[i].first}]);
a.push_back(5);
b.push_back(four[i].first+1);
}else{
join(m[{4, four[i].first}], m[{4, four[i+1].first}]);
u.push_back(four[i].second);
v.push_back(four[i+1].second);
a.push_back(5);
b.push_back(four[i].first+1);
}
}
int cnt = 0;
for(int i = 0; i < (int)x.size(); ++i){
if(f[i] == i){
cnt++;
}
}
if((int)u.size() < (int)x.size()-1 || cnt != 1){
return 0;
}
build(u, v, a, b);
return 1;
}
