#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
vector <pair <int, int>> pontos[N];
vector <pair <int, int>> pontos2[N];
map <pair <int, int>, pair <int, int>> fontes;
vector <int> g[N];
int mark[N];
int cnt;
int n;
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) {
n = x.size();
for(int i = 0;i < n;i++){
pontos[x[i]].push_back({y[i], i});
pontos2[y[i]].push_back({x[i], i});
}
for(int i = 2;i < N;i++){
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){
if((pontos[i][j-1].first/2)%2 == 1){
fontes[{i-1, pontos[i][j-1].first+1}] = make_pair(pontos[i][j].second, pontos[i][j-1].second);
}
else{
fontes[{i+1, pontos[i][j-1].first+1}] = make_pair(pontos[i][j].second, pontos[i][j-1].second);
}
}
}
}
for(int i = 2;i < N;i++){
if(pontos2[i].empty()) continue;
sort(pontos2[i].begin(), pontos2[i].end());
for(int j = 1;j < pontos2[i].size();j++){
if(pontos2[i][j].first - pontos2[i][j-1].first == 2){
if(fontes.find({pontos2[i][j].first-1, i-1}) != fontes.end()){
fontes[{pontos2[i][j].first-1, i+1}] = make_pair(pontos2[i][j].second, pontos2[i][j-1].second);
}
else{
fontes[{pontos2[i][j].first-1, i-1}] = make_pair(pontos2[i][j].second, pontos2[i][j-1].second);
}
}
}
}
vector <int> u, v, a, b;
int st = 0;
for(auto [p, q] : fontes){
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;
return 1;
}
