#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
vector <pair <int, int>> pontos[7];
vector <int> g[N];
map <pair <int, int>, pair <int, int>> bancos;
map <pair <int, int>, int> fontes;
int mark[N];
int cnt;
void dfs(int v){
cnt++;
mark[v] = 1;
for(auto x : g[v]){
if(mark[x]) continue;
dfs(x);
}
return;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n = x.size();
for(int i = 0;i < x.size();i++){
pontos[x[i]].push_back({y[i], i});
fontes[{x[i], y[i]}] = i;
}
for(int i = 2;i <= 6;i += 2){
if(pontos[i].empty()) continue;
sort(pontos[i].begin(), pontos[i].end());
for(int j = 1;j < pontos[i].size();j++){
if(pontos[i][j].first-pontos[i][j-1].first == 2){
bancos[{(i == 2 ? 1 : i+1), pontos[i][j].first-1}] = {pontos[i][j].second, pontos[i][j-1].second};
}
}
}
for(int i = 0;i < pontos[4].size();i++){
auto [y, idx] = pontos[4][i];
if(fontes.find({2, y}) != fontes.end()){
bancos[{3, y-1}] = {idx, fontes[{2, y}]};
}
}
for(int i = 0;i < pontos[4].size();i++){
auto [y, idx] = pontos[4][i];
if(fontes.find({6, y}) != fontes.end()){
if(bancos.find({5, y-1}) != bancos.end()){
if(bancos.find({3, y-1}) != bancos.end()){
if(bancos.find({3, y+1}) != bancos.end()){
bancos[{3, y+1}] = bancos[{3, y-1}];
bancos[{3, y-1}] = bancos[{5, y-1}];
bancos[{5, y-1}] = {idx, fontes[{6, y}]};
}
else{
bancos[{3, y+1}] = bancos[{3, y-1}];
bancos[{3, y-1}] = bancos[{5, y-1}];
bancos[{5, y-1}] = {idx, fontes[{6, y}]};
}
if(i != pontos[4].size() -1){
if(pontos[4][i+1].first-pontos[4][i].first == 2) i++;
}
}
else{
bancos[{3, y-1}] = bancos[{5, y-1}];
bancos[{5, y-1}] = {idx, fontes[{6, y}]};
}
}
else{
bancos[{5, y-1}] = {idx, fontes[{6, y}]};
}
}
}
vector <int> u, v, a, b;
int st = 0;
for(auto [p, q] : bancos){
auto [x, y] = p;
auto [z, w] = q;
a.push_back(x);
b.push_back(y);
u.push_back(z);
v.push_back(w);
// cout << x << ' ' << y << ' ' << z << ' ' << w << '\n';
g[w].push_back(z);
g[z].push_back(w);
st = z;
}
dfs(st);
if(cnt != n) return 0;
build(u, v, a, b);
return 1;
}
