#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
const int N = 1e6 + 1;
vector<array<int,3>> a;
vector<pair<int,int>> edges;
vector<int> u,v,x,y;
int n,p[N];
map<pair<int,int>,int> id;
int get(int v){
if(p[v] == v) return v;
return p[v] = get(p[v]);
}
bool merge(int x,int y){
x = get(x);
y = get(y);
if(x == y) return false;
p[x] = y;
return true;
}
bool check(){
for(int i = 1;i < n;i++){
if(get(i) != get(0)) return false;
}
return true;
}
int P[N],timer = 1;
map<pair<int,int>,pair<int,int>> mt;
map<pair<int,int>,int> vis;
vector<int> xx,yy;
bool dfs(pair<int,int> C){
int i =C.first,j= C.second;
if(vis[{i,j}] == timer) return false;
vis[{i,j}] = timer;
if(yy[i] == yy[j]){
if(!mt.count({xx[i] - 1,yy[i] - 1}) || dfs(mt[{xx[i] - 1,yy[i] - 1}])){
mt[{xx[i] - 1,yy[i] - 1}] = C;
return true;
}
if(!mt.count({xx[i] - 1,yy[i] + 1}) || dfs(mt[{xx[i] - 1,yy[i] + 1}])){
mt[{xx[i] - 1,yy[i] + 1}] = C;
return true;
}
}else{
if(!mt.count({xx[i] - 1,yy[i] - 1}) || dfs(mt[{xx[i] - 1,yy[i] - 1}])){
mt[{xx[i] - 1,yy[i] - 1}] = C;
return true;
}
if(!mt.count({xx[i] + 1,yy[i] - 1}) || dfs(mt[{xx[i] + 1,yy[i] - 1}])){
mt[{xx[i] + 1,yy[i] - 1}] = C;
return true;
}
}
return false;
}
bool vis1[N];
int construct_roads(std::vector<int> X, std::vector<int> Y){
xx = X;
yy = Y;
n = (int)X.size();
for(int i = 0;i < n;i++){
p[i] = id[{X[i],Y[i]}] = i;
P[i] = i;
}
sort(P,P + n,[&](int c,int d){
return make_pair(X[c],Y[c]) < make_pair(X[d],Y[d]);
});
for(int j = 0;j < n;j++){
int i = P[j];
if(id.count({X[i] - 2,Y[i]})){
merge(i,id[{X[i] - 2,Y[i]}]);
edges.push_back({i,id[{X[i] - 2,Y[i]}]});
}
if(id.count({X[i],Y[i] - 2})){
merge(i,id[{X[i],Y[i] - 2}]);
edges.push_back({i,id[{X[i],Y[i] - 2}]});
}
}
if(!check()) return 0;
for(int i =0 ;i < n;i++){
p[i] =i;
}
id.clear();
for(int f =0 ;f < (int)edges.size();f++){
int i = edges[f].first,j = edges[f].second;
if(get(i) == get(j)) continue;
if(X[i] == X[j]){
if(!mt.count({X[i] - 1,Y[i] - 1})){
mt[{X[i] - 1,Y[i] - 1}] = {i,j};
vis1[f] = 1;
}else if(!mt.count({X[i] + 1,Y[i] - 1})){
mt[{X[i] + 1,Y[i] - 1}] = {i,j};
vis1[f] = 1;
}
}else{
if(!mt.count({X[i] - 1,Y[i] - 1})){
mt[{X[i] - 1,Y[i] - 1}] = {i,j};
vis1[f] = 1;
}else if(!mt.count({X[i] - 1,Y[i] + 1})){
mt[{X[i] - 1,Y[i] + 1}] = {i,j};
vis1[f] = 1;
}
}
if(vis1[f]){
merge(i,j);
}
}
for(int i = 0;i < (int)edges.size();++i){
if(vis1[i] ||get(edges[i].first) == get(edges[i].second)) continue;
timer++;
bool ok = dfs({edges[i].first,edges[i].second});
if(ok){
merge(edges[i].first,edges[i].second);
}
}
for(auto [pp,pp1]:mt){
x.push_back(pp.first);y.push_back(pp.second);
u.push_back(pp1.first);v.push_back(pp1.second);
}
if(!check()) return 0;
build(u,v,x,y);
return 1;
}
