#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],all[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;
set<int> st,st2;
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]);
st2.insert(x[i]);
all[x[i]].pb(y[i]);
}
for(auto i:st2)sort(all[i].begin(),all[i].end());
map<pair<int,int>,pair<int,int>> start,belong;
for(auto i:st){
int curx,cury;
sort(vec[i].begin(),vec[i].end());
for(auto j:vec[i]){
int X=j,Y=i;
int k=exist[{X-2,Y}];
if(k){
if(start[{curx,cury}].second==-1)start[{curx,cury}].second=0;
start[{curx,cury}].second^=1;
}
else{
start[{X,Y}]={1,-1}; //1 means up 0 means down
curx=X; cury=Y;
}
belong[{X,Y}]={curx,cury};
}
}
for(auto i:st2){
for(auto j:all[i]){
int X=i,Y=j;
int k=exist[{X,Y-2}];
if(k){
if(!start[belong[{X,Y}]].second && start[{X,Y-2}].second!=-1 && start[{X,Y-2}].first){
start[{X,Y-2}].first^=1;
start[{X,Y-2}].second^=1;
}
u.pb(k);
v.pb(exist[{X,Y}]);
b.pb(Y-1);
if(start[{belong[{X,Y}]}].second)a.pb(X-1);
else a.pb(X+1);
}
}
}
for(int i=0;i<x.size();i++){
int X=x[i],Y=y[i];
if(belong[{X,Y}]==make_pair(X,Y)){
int cur=start[{X,Y}].first;
// cout<<X<<' '<<Y<<' '<<cur<<endl;
for(int j=X+2;true;j+=2){
if(!exist[{j,Y}])break;
u.pb({exist[{j,Y}]});
v.pb({exist[{j-2,Y}]});
a.pb(j-1);
if(cur)b.pb(Y+1);
else b.pb(Y-1);
cur^=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;
}
