#include "parks.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
#define p_q priority_queue
using namespace std;
struct DSU{
vector<int> bo,ss;
void init(int x){
bo.resize(x);
ss.resize(x,1);
iota(bo.begin(),bo.end(),0);
}
int find(int x){
return bo[x]==x?x:bo[x]=find(bo[x]);
}
int merge(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return 0;
}
bo[x]=y;
ss[y]+=ss[x];
return 1;
}
}dsu;
vector<int> au,av,aa,ab;
void ag(int a,int b,int c,int d){
au.push_back(a);
av.push_back(b);
aa.push_back(c);
ab.push_back(d);
}
int construct_roads(vector<int> x, vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
map<pair<int,int>,int> m;
int n=x.size();
for(int i=0;i<n;i++){
m[{x[i],y[i]}]=i+1;
}
dsu.init(n);
vector<int> up(n,-1),l(n,-1),r(n,-1);
vector<pair<int,int> > lb;
for(int p=0;p<n;p++){
if(m.find({x[p],y[p]+2})!=m.end()){
int a=m[{x[p],y[p]+2}]-1;
dsu.merge(a,p);
if(x[p]==2){
ag(a,p,1,y[p]+1);
}
else if(x[p]==6){
ag(a,p,7,y[p]+1);
}
else{
up[a]=p;
}
}
}
for(int p=0;p<n;p++){
if(x[p]==4){
lb.push_back({y[p],p});
if(m.find({2,y[p]})!=m.end()){
int a=m[{2,y[p]}]-1;
if(dsu.merge(a,p)){
l[p]=a;
}
}
if(m.find({6,y[p]})!=m.end()){
int a=m[{6,y[p]}]-1;
if(dsu.merge(a,p)){
r[p]=a;
}
}
}
}
if(dsu.ss[dsu.find(0)]!=n){
return 0;
}
sort(lb.begin(),lb.end());
int flag=0;
int lst=0;
for(auto h:lb){
int i=h.sc;
if(lst!=h.fs-2){
flag=0;
}
if(flag){
if(up[i]>=0){
ag(up[i],i,3,h.fs-1);
}
flag=0;
lst=h.fs;
continue;
}
if(up[i]>=0){
if(l[i]>=0 && r[i]>=0){
ag(l[i],i,3,h.fs-1);
ag(up[i],i,5,h.fs-1);
ag(r[i],i,5,h.fs+1);
flag=1;
}
else if(l[i]>=0){
ag(l[i],i,3,h.fs-1);
ag(up[i],i,5,h.fs-1);
}
else if(r[i]>=0){
ag(r[i],i,5,h.fs-1);
ag(up[i],i,3,h.fs-1);
}
else{
ag(up[i],i,3,h.fs-1);
}
}
else{
if(l[i]>=0){
ag(l[i],i,3,h.fs-1);
}
if(r[i]>=0){
ag(r[i],i,5,h.fs-1);
}
}
lst=h.fs;
}
build(au,av,aa,ab);
return 1;
}
