#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "parks.h"
int par[300001];
int ss[300001];
int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}
map<pair<int,int>,int> mid;
map<int,pair<int,int>> mid2;
int ind5=-1;
void add(int i,int j){
if(mid.find({i,j})==mid.end()){
//ind5++;
mid[{i,j}]=ind5;
mid2[ind5]={i,j};
ind5++;
}
}
vector<int> adj2[2000001];
int dd[2000001];
int vis[2000001];
//vector<int> adj3[300001];
int construct_roads(vector<int> x, std::vector<int> y) {
int n=x.size();
// sort(y,y+n);
vector<int> uu, vv, aa, bb;
vector<pair<int,int>> zz;
map<pair<int,int>,int> xx;
for(int i=0;i<n;i++){
xx[{x[i],y[i]}]=i;
par[i]=i;
}
map<pair<int,int>,int> kk;
for(int i=0;i<n;i++){
if(xx.find({x[i],y[i]+2})!=xx.end()){
int x1=find(i);
int y1=find(xx[{x[i],y[i]+2}]);
if(x1!=y1){
par[x1]=y1;
uu.pb(i);
vv.pb(xx[{x[i],y[i]+2}]);
}
}
}
for(int i=0;i<n;i++){
if(xx.find({x[i]+2,y[i]})!=xx.end()){
int x1=find(i);
int y1=find(xx[{x[i]+2,y[i]}]);
if(x1!=y1){
par[x1]=y1;
uu.pb(i);
vv.pb(xx[{x[i]+2,y[i]}]);
}
}
}
for(int i=0;i<n;i++){
par[i]=find(i);
}
for(int i=0;i<n;i++){
if(par[i]!=par[0]){
return 0;
}
}
ind5=uu.size();
for(int i=0;i<uu.size();i++){
aa.pb(-1);
bb.pb(-1);
if(x[uu[i]]+2==x[vv[i]]){
//
add(x[uu[i]]+1,y[uu[i]]+1);
add(x[uu[i]]+1,y[uu[i]]-1);
adj2[i].pb(mid[{x[uu[i]]+1,y[uu[i]]+1}]);
//adj2[mid[{x[uu[i]]+1,y[uu[i]]+1}]].pb(i);
adj2[i].pb(mid[{x[uu[i]]+1,y[uu[i]]-1}]);
//adj2[mid[{x[uu[i]]+1,y[uu[i]]-1}]].pb(i);
}
else{
add(x[uu[i]]+1,y[uu[i]]+1);
add(x[uu[i]]-1,y[uu[i]]+1);
adj2[i].pb(mid[{x[uu[i]]+1,y[uu[i]]+1}]);
adj2[i].pb(mid[{x[uu[i]]-1,y[uu[i]]+1}]);
}
}
for(int i=0;i<uu.size();i++){
for(auto j:adj2[i]){
adj2[j].pb(i);
}
}
set<pair<int,int>> ee;
for(int i=0;i<ind5;i++){
if(adj2[i].size()==0){
return 0;
}
dd[i]=adj2[i].size();
ee.insert({adj2[i].size(),i});
}
while(ee.size()){
pair<int,int> no=*ee.begin();
if(no.a==0){
if(no.b<uu.size()){
return 0;
}
ee.erase(no);
vis[no.b]=1;
continue;
}
int st=-1;
for(auto j:adj2[no.b]){
if(vis[j]==0){
st=j;
}
}
vis[st]=1;
vis[no.b]=1;
ee.erase({dd[no.b],no.b});
ee.erase({dd[st],st});
int ac=no.b;
int bc=st;
if(ac>bc){
swap(ac,bc);
}
aa[ac]=mid2[bc].a;
bb[ac]=mid2[bc].b;
for(auto j:adj2[no.b]){
if(vis[j]==0){
ee.erase({dd[j],j});
dd[j]--;
ee.insert({dd[j],j});
}
}
for(auto j:adj2[st]){
if(vis[j]==0){
ee.erase({dd[j],j});
dd[j]--;
ee.insert({dd[j],j});
}
}
}
/* for(int i=0;i<n;i++){
zz.pb({y[i],i});
}
sort(zz.begin(),zz.end());
for(int i=0;i<n-1;i++){
if(zz[i+1].a-zz[i].a>2){
return 0;
}
uu.pb(zz[i].b);
vv.pb(zz[i+1].b);
aa.pb(1);
bb.pb(zz[i].a+1);
}*/
build(uu,vv,aa,bb);
return 1;
/*if (x.size() == 1)
return 0;
u.push_back(0);
v.push_back(1);
a.push_back(x[0]+1);
b.push_back(y[0]-1);
build(u, v, a, b);
return 1;*/
}
