#include "parks.h"
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
int fount2[200005], fount4[200005];
int sy2[200005], sy4[200005];
int numofvis;
vector<int> adj[200005];
map<int,int> emf;
bool visited[200005];
bool compare2(int a, int b){ return sy2[a] < sy2[b]; }
bool compare4(int a, int b){ return sy4[a] < sy4[b]; }
void dfs(int v){
visited[v] = true;
numofvis++;
int len = adj[v].size();
for(int i=0; i<len; i++){
int to = adj[v][i];
if(!visited[to]) dfs(to);
}
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = x.size(), cnt2=0, cnt4=0;
for(int i=0; i<n; i++){
if(x[i] == 2){
fount2[cnt2] = i;
sy2[cnt2++] = y[i];
}
else{
fount4[cnt4] = i;
sy4[cnt4++] = y[i];
}
}
std::sort(&fount2[0],&fount2[cnt2],compare2);
std::sort(&sy2[0],&sy2[cnt2]);
std::sort(&fount4[0],&fount4[cnt4],compare4);
// for(int i=1; i<cnt4; i++) emf[sy4[fount4[i]]] = fount4[i];
// emf[sy4[fount4[0]]] = -1;
std::sort(&sy4[0],&sy4[cnt4]);
for(int i=1; i<cnt4; i++) emf[sy4[i]] = i;
emf[sy4[0]] = -1;
std::vector<int> u, v, a, b;
if(cnt2 == 0){
for(int i=0; i<cnt4-1; i++){
if(sy4[i+1]-sy4[i] != 2) return 0;
u.push_back(fount4[i]);
v.push_back(fount4[i+1]);
a.push_back(5);
b.push_back(sy4[i]+1);
}
build(u, v, a, b);
return 1;
}
if(cnt4 == 0){
for(int i=0; i<cnt2-1; i++){
if(sy2[i+1]-sy2[i] != 2) return 0;
u.push_back(fount2[i]);
v.push_back(fount2[i+1]);
a.push_back(1);
b.push_back(sy2[i]+1);
}
build(u, v, a, b);
return 1;
}
for(int i=0; i<cnt2; i++){
if(i == cnt2-1) continue;
while(sy2[i+1]-sy2[i] == 2){
u.push_back(fount2[i]);
v.push_back(fount2[i+1]);
a.push_back(1);
b.push_back(sy2[i]+1);
i++;
}
}
for(int i=0; i<cnt4; i++){
if(i == cnt4-1) continue;
while(sy4[i+1]-sy4[i] == 2){
u.push_back(fount4[i]);
v.push_back(fount4[i+1]);
a.push_back(5);
b.push_back(sy4[i]+1);
i++;
}
}
for(int i=0; i<cnt2; i++){
int temp = emf[sy2[fount2[i]]];
if(temp == 0) continue;
if(temp == -1) temp = 0;
u.push_back(fount2[i]);
v.push_back(fount4[temp]);
a.push_back(3);
b.push_back(sy2[fount2[i]]-1);
}
int s = u.size();
for(int i=0; i<s; i++){
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(u[0]);
if(numofvis != n) return 0;
build(u, v, a, b);
return 1;
}
