#include "parks.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
struct DSU{
vector<int> e;
DSU(int n){
e=vector<int>(n,-1);
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
int sz(int x){
return -e[find(x)];
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
return true;
}
};
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
map<int,map<int,int>> mp;
map<int,int> cnt;
int n=(int)x.size();
for(int i=0;i<n;i++){
mp[y[i]][x[i]]=i+1;
cnt[y[i]]++;
}
vector<int> ys;
for(int i=0;i<n;i++){
ys.push_back(y[i]);
}
sort(all(ys));
ys.resize(unique(all(ys))-ys.begin());
vector<int> u,v,a,b;
int cnt2=0;
for(auto Y:ys){
if(cnt[Y-2]==0){
cnt2++;
continue;
}
bool tf=false;
if(mp[Y][2]!=0 and mp[Y-2][2]!=0){
u.push_back(mp[Y-2][2]-1);
v.push_back(mp[Y][2]-1);
a.push_back(1);
b.push_back(Y-1);
tf=true;
}
else if(mp[Y][6]!=0 and mp[Y-2][6]!=0){
u.push_back(mp[Y-2][6]-1);
v.push_back(mp[Y][6]-1);
a.push_back(7);
b.push_back(Y-1);
tf=true;
}
if(tf){
if(mp[Y][2]!=0 and mp[Y][4]!=0){
u.push_back(mp[Y][2]-1);
v.push_back(mp[Y][4]-1);
a.push_back(3);
b.push_back(Y-1);
//tf=true;
}
if(mp[Y][4]!=0 and mp[Y][6]!=0){
u.push_back(mp[Y][4]-1);
v.push_back(mp[Y][6]-1);
a.push_back(5);
b.push_back(Y-1);
//tf=true;
}
continue;
}
if(mp[Y][4]==0 or mp[Y-2][4]==0){
return 0;
}
if(mp[Y][2]!=0 and mp[Y][6]!=0){
u.push_back(mp[Y-2][4]-1);
v.push_back(mp[Y][4]-1);
a.push_back(1);
b.push_back(Y-1);
u.push_back(mp[Y][4]-1);
v.push_back(mp[Y][6]-1);
a.push_back(5);
b.push_back(Y-1);
u.push_back(mp[Y][2]-1);
v.push_back(mp[Y][4]-1);
a.push_back(1);
b.push_back(Y+1);
}
else if(mp[Y][2]!=0){
u.push_back(mp[Y-2][4]-1);
v.push_back(mp[Y][4]-1);
a.push_back(5);
b.push_back(Y-1);
u.push_back(mp[Y][2]-1);
v.push_back(mp[Y][4]-1);
a.push_back(1);
b.push_back(Y-1);
}
else if(mp[Y][6]!=0){
u.push_back(mp[Y-2][4]-1);
v.push_back(mp[Y][4]-1);
a.push_back(1);
b.push_back(Y-1);
u.push_back(mp[Y][4]-1);
v.push_back(mp[Y][6]-1);
a.push_back(5);
b.push_back(Y-1);
}
else{
u.push_back(mp[Y-2][4]-1);
v.push_back(mp[Y][4]-1);
a.push_back(5);
b.push_back(Y-1);
}
}
if(cnt2>1) return 0;
/*vector<pair<int,int>> e;
for(int i=0;i<n;i++){
if(mp.find({x[i]-2,y[i]})!=mp.end()){
e.push_back({mp[{x[i]-2,y[i]}],i});
}
if(x[i]==2 or x[i]==6){
if(mp.find({x[i],y[i]-2})!=mp.end()){
e.push_back({mp[{x[i],y[i]-2}],i});
}
}
}
DSU dsu(n);
for(auto v:e){
cout<<v.f<<' '<<v.s<<'\n';
dsu.unite(v.f,v.s);
}
if(dsu.sz(0)!=n) return 0;
vector<int> u,v,a,b;
for(auto p:e){
u.push_back(p.f);
v.push_back(p.s);
if(y[p.f]==y[p.s]){
a.push_back((x[p.f]+x[p.s])/2);
b.push_back(y[p.f]+1);
}
else{
if(x[p.f]==2) a.push_back(1);
else a.push_back(7);
b.push_back((y[p.f]+y[p.s])/2);
}
}*/
build(u,v,a,b);
return 1;
}
