#include "parks.h"
#include <bits/stdc++.h>
#define pb push_back
#define ep insert
#define F first
#define S second
using namespace std;
const int N=2e5+5;
int a[N],b[N],par[N],sz[N],n;
vector<int> c[N],r[N];
vector<int> adj[N];
bool cmp(int x,int y){
return a[x]<a[y];
}
bool cmp2(int x,int y){
return b[x]>b[y];
}
int getpar(int x){
if (x==par[x]) return x;
return par[x]=getpar(par[x]);
}
void link(int x,int y){
x=getpar(x);
y=getpar(y);
if (x==y) return;
if (sz[x]>sz[y]) swap(x,y);
sz[y]+=sz[x];
par[x]=y;
return;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
n=x.size();
for (int i=0;i<n;i++){
par[i]=i;
sz[i]=1;
a[i]=x[i];
b[i]=y[i];
c[y[i]].pb(i);
r[x[i]].pb(i);
}
vector<int> U,V,s;
for (int i=0;i<N;i+=2) sort(c[i].begin(),c[i].end(),cmp);
for (int i=0;i<N;i+=2){
for (int j=0;j<int(c[i].size())-1;j++){
if (a[c[i][j+1]]-a[c[i][j]]==2){
link(c[i][j],c[i][j+1]);
U.pb(c[i][j]);
V.pb(c[i][j+1]);
s.pb(0);
adj[c[i][j]].pb(U.size()-1);
adj[c[i][j+1]].pb(U.size()-1);
}
}
}
for (int i=N-1;i>=0;i--){
for (int j=0;j<int(c[i].size());j++){
int l=0,r=int(c[i+2].size())-1,mid,idx=-1;
while (l<=r){
mid=(l+r)/2;
if (a[c[i+2][mid]]==a[c[i][j]]){
idx=mid;
break;
}
if (a[c[i+2][mid]]>a[c[i][j]]) r=mid-1;
else l=mid+1;
}
if (idx!=-1){
if (getpar(c[i][j])==getpar(c[i+2][idx])) continue;
link(c[i][j],c[i+2][idx]);
V.pb(c[i][j]);
U.pb(c[i+2][idx]);
s.pb(2);
adj[c[i][j]].pb(U.size()-1);
adj[c[i+2][idx]].pb(U.size()-1);
}
}
}
//for (int i=0;i<U.size();i++) cout<<U[i]<<' '<<V[i]<<endl;
if (sz[getpar(0)]!=n) return 0;
//for (int i=0;i<N;i+=2) sort(r[i].begin(),r[i].end(),cmp2);
vector<int> d(U.size()),e(U.size());
set<pair<int,int>> bench;
bool h=0;
int last=-1;
for (int i=0;i<U.size();i++){
if (s[i]==0) continue;
if (a[U[i]]!=last){
last=a[U[i]];
h=0;
}
if (!h){
d[i]=a[U[i]]-1;
e[i]=b[U[i]]-1;
bench.ep({d[i],e[i]});
h=!h;
}
else{
d[i]=a[U[i]]+1;
e[i]=b[U[i]]-1;
bench.ep({d[i],e[i]});
h=!h;
}
}
//for (auto u:bench) cout<<u.F<<' '<<u.S<<endl;
for (int i=0;i<U.size();i++){
if (s[i]==2) continue;
int xx=a[U[i]]+1,yy=b[U[i]]+1;
if (!bench.count({xx,yy})){
d[i]=xx;
e[i]=yy;
bench.ep({xx,yy});
continue;
}
yy-=2;
d[i]=xx;
e[i]=yy;
bench.ep({xx,yy});
}
build(U,V,d,e);
return 1;
}
