#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define pb push_back
const int MAXN=2e5+5;
int cnt[MAXN];
vector<int> adj[MAXN];
bool vis[MAXN];
void dfs(int node){
if(vis[node])return;
vis[node]=1;
for(auto i:adj[node])dfs(i);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int,int>,int> exist;
vector<int> vec[7];
for(int i=0;i<x.size();i++){
exist[{x[i],y[i]}]=i+1;
vec[x[i]].pb(y[i]);
}
sort(vec[2].begin(),vec[2].end());
sort(vec[4].begin(),vec[4].end());
sort(vec[6].begin(),vec[6].end());
std::vector<int> u, v, a, b;
for(int i=1;i<vec[2].size();i++){
if(vec[2][i-1]+2==vec[2][i]){
u.pb(exist[{2,vec[2][i-1]}]);
v.pb(exist[{2,vec[2][i]}]);
a.pb(1);
b.pb(vec[2][i-1]+1);
}
}
for(int i=1;i<vec[6].size();i++){
if(vec[6][i-1]+2==vec[6][i]){
u.pb(exist[{6,vec[6][i-1]}]);
v.pb(exist[{6,vec[6][i]}]);
a.pb(7);
b.pb(vec[6][i-1]+1);
}
}
cnt[0]=1;
map<pair<int,int>,bool> taken;
for(int i=1;i<vec[4].size();i++){
cnt[i]=1;
if(vec[4][i-1]+2==vec[4][i]){
cnt[i]+=cnt[i-1];
u.pb(exist[{4, vec[4][i - 1]}]);
v.pb(exist[{4, vec[4][i]}]);
b.pb(vec[4][i - 1] + 1);
if(cnt[i]%2==0)a.pb(3);
else a.pb(5);
taken[{a.back(),b.back()}]=1;
}
}
for(int i=0;i<vec[4].size();i++){
int j=exist[{2,vec[4][i]}];
if(j){
if(!taken[{3,vec[4][i]-1}]){
taken[{3,vec[4][i]-1}]=1;
u.pb(j);
v.pb(exist[{4,vec[4][i]}]);
a.pb(3);
b.pb(vec[4][i]-1);
}
else if(!taken[{3,vec[4][i]+1}]){
taken[{3,vec[4][i]+1}]=1;
u.pb(j);
v.pb(exist[{4,vec[4][i]}]);
a.pb(3);
b.pb(vec[4][i]+1);
}
}
j=exist[{6,vec[4][i]}];
if(j){
if(!taken[{5,vec[4][i]-1}]){
taken[{5,vec[4][i]-1}]=1;
u.pb(j);
v.pb(exist[{4,vec[4][i]}]);
a.pb(5);
b.pb(vec[4][i]-1);
}
else if(!taken[{3,vec[4][i]+1}]){
taken[{5,vec[4][i]+1}]=1;
u.pb(j);
v.pb(exist[{4,vec[4][i]}]);
a.pb(5);
b.pb(vec[4][i]+1);
}
}
}
for(int i=0;i<v.size();i++){
u[i]--;
v[i]--;
adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
}
dfs(0);
for(int i=0;i<x.size();i++){
if(!vis[i]){
return 0;
}
}
build(u, v, a, b);
return 1;
}
