#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int MAX=2e5+5;
int n,P[MAX];
vector<int> x,y;
map<ii,int> M;
bool isVertical(ii u) {
return x[u.first]==x[u.second];
}
bool cmp(ii u,ii v) {
if(x[u.first]==x[v.first]) {
if(isVertical(u)==isVertical(v))
return y[u.first]<y[v.first];
return isVertical(u)>isVertical(v);
}
return x[u.first]<x[v.first];
}
vector<ii> constructBenches(vector<ii> &paths) {
map<ii,bool> mark;
vector<ii> benchesPos;
map<ii,vector<int>> g;
for(int i=0;i<paths.size();i++) {
ii path=paths[i];
if(x[path.first]==x[path.second]) {
int bx=x[path.first],by=y[path.first]+1;
benchesPos.push_back({bx-1,by});
benchesPos.push_back({bx+1,by});
g[ii(bx-1,by)].push_back(i);
g[ii(bx+1,by)].push_back(i);
} else {
int bx=x[path.first]+1,by=y[path.first];
benchesPos.push_back({bx,by-1});
benchesPos.push_back({bx,by+1});
g[ii(bx,by-1)].push_back(i);
g[ii(bx,by+1)].push_back(i);
}
}
vector<ii> benches;
if(*max_element(x.begin(),x.end())<=6) {
for(int i=0;i<paths.size();i++) {
if(!mark[benchesPos[2*i]]) {
mark[benchesPos[2*i]]=true;
benches.push_back(benchesPos[2*i]);
} else {
mark[benchesPos[2*i+1]]=true;
benches.push_back(benchesPos[2*i+1]);
}
}
} else {
benches.resize(paths.size(),{-1,-1});
for(int i=0;i<paths.size();i++)
if(benches[i]==ii(-1,-1)) {
int curId=i;
ii curBenchPos=benchesPos[2*i];
benches[curId]=curBenchPos;
vector<int> gg=g[curBenchPos];
while(gg.size()==2) {
int u=gg[0],v=gg[1];
if(u!=curId)
swap(u,v);
curId=v;
if(benches[curId]!=ii(-1,-1))
break;
curBenchPos=(curBenchPos!=benchesPos[2*v]?benchesPos[2*v]:benchesPos[2*v+1]);
benches[curId]=curBenchPos;
gg=g[curBenchPos];
}
}
for(ii bench:benches) {
assert(!mark[bench]);
mark[bench]=true;
}
}
return benches;
}
int find(int u) {
if(u==P[u])
return u;
return P[u]=find(P[u]);
}
void merge(int u,int v) {
if(u>v)
swap(u,v);
P[u]=v;
}
vector<ii> removePaths(vector<ii> paths) {
for(int i=0;i<n;i++)
P[i]=i;
vector<ii> newPaths;
for(ii path:paths) {
int u=find(path.first),v=find(path.second);
if(u!=v) {
merge(u,v);
newPaths.push_back(path);
}
}
return newPaths;
}
int construct_roads(std::vector<int> _x, std::vector<int> _y) {
n=_x.size();
x=_x,y=_y;
for(int i=0;i<n;i++)
M[ii(x[i],y[i])]=i;
vector<ii> paths;
for(int i=0;i<n;i++) {
auto it=M.find({x[i]+2,y[i]});
if(it!=M.end())
paths.push_back({i,it->second});
it=M.find({x[i],y[i]+2});
if(it!=M.end())
paths.push_back({i,it->second});
}
sort(paths.begin(),paths.end(),cmp);
paths = removePaths(paths);
if(paths.size()!=n-1)
return 0;
//for(ii path:paths)
// cerr<<x[path.first]<<' '<<y[path.first]<<' '<<x[path.second]<<' '<<y[path.second]<<'\n';
vector<ii> benches=constructBenches(paths);
vector<int> U(n-1),V(n-1),A(n-1),B(n-1);
for(int i=0;i<n-1;i++) {
U[i]=paths[i].first,V[i]=paths[i].second;
A[i]=benches[i].first,B[i]=benches[i].second;
}
build(U,V,A,B);
return 1;
}
