#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define pb push_back
const int MAXN=2e5+5;
vector<int> adj[MAXN],vec[MAXN],u,v,a,b;
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> uniq;
set<int> st;
for(int i=0;i<x.size();i++){
exist[{x[i],y[i]}]=i+1;
vec[y[i]].pb(x[i]);
st.insert(y[i]);
}
for(auto i:st)uniq.pb(i);
sort(uniq.begin(),uniq.end());
map<pair<int,int>,bool> taken;
for(int id=0;id<uniq.size();id++){
int i=uniq[id];
sort(vec[i].begin(),vec[i].end());
int cnt=0;
for(int j=1;j<vec[i].size();j++){
if(vec[i][j-1]+2==vec[i][j]){
cnt++;
u.pb(exist[{vec[i][j - 1],i}]);
v.pb(exist[{vec[i][j],i}]);
a.pb(vec[i][j]-1);
if(cnt%2==1)b.pb(i-1);
else b.pb(i+1);
taken[{a.back(),b.back()}]=1;
}
else cnt=0;
}
if(id>0){
for(int j=0;j<vec[i].size();j++){
int k=exist[{vec[i][j],i-2}];
if(k){
if(!taken[{vec[i][j]-1,i-1}]){
u.pb(k);
v.pb(exist[{vec[i][j],i}]);
b.pb(i-1);
taken[{vec[i][j]-1,i-1}]=1;
a.pb(vec[i][j]-1);
}
else if(!taken[{vec[i][j]+1,i-1}]){
u.pb(k);
v.pb(exist[{vec[i][j],i}]);
b.pb(i-1);
taken[{vec[i][j]+1,i-1}]=1;
a.pb(vec[i][j]+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;
}
