#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAX = 2e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int N;
vector<int> v[MAX], X, Y;
vector<pii> range[MAX];
bool check(vector<pii> e) {
vector<int> g[N];
for(auto [A,B] : e)
g[A].pb(B), g[B].pb(A);
queue<int> fila;
vector<bool> vis(N);
fila.push(0);
vis[0] = 1;
while(!fila.empty()) {
int at = fila.front();
fila.pop();
for(int viz : g[at])
if(!vis[viz]) fila.push(viz), vis[viz] = 1;
}
for(int i = 0; i < N; i++) if(!vis[i]) return 0;
return 1;
}
void construct(vector<pii> edges){
vector<int> U, V, A, B;
map<pii,vector<pii>> point;
// vamos anotar pontos e quantas ruas eles olham
for(auto [i1, i2] : edges){
int x1 = X[i1], y1 = Y[i1], x2 = X[i2], y2 = Y[i2];
if(x1 == x2) {
point[{x1+1, (y1+y2)/2}].pb({i1,i2});
point[{x1-1, (y1+y2)/2}].pb({i1,i2});
}
if(y1 == y2) {
point[{(x1+x2)/2, y1+1}].pb({i1,i2});
point[{(x1+x2)/2, y1-1}].pb({i1,i2});
}
}
queue<pii> fila;
for(auto [p, qtd] : point)
if(sz(qtd) == 1) fila.push(p);
while(!point.empty()) {
if(fila.empty()) fila.push((*point.begin()).fr);
auto [a,b] = fila.front();
fila.pop();
if(point.count({a,b}) == 0) continue;
auto [u,v] = point[{a,b}].back();
point[{a,b}].pop_back();
U.pb(u); V.pb(v); A.pb(a); B.pb(b);
pii p = {a,b};
if(X[u] == X[v]) p.fr = 2*X[u] - p.fr;
else p.sc = 2*Y[u] - p.sc;
for(int ind = 0; ind < sz(point[p]); ind++) {
if(point[p][ind] == mk(u,v)) {
point[p].erase(point[p].begin() + ind);
break;
}
}
if(point[p].empty()) point.erase(p);
if(point[{a,b}].empty()) point.erase({a,b});
}
build(U, V, A, B);
}
int construct_roads(vector<int> x, vector<int> y) {
N = sz(x);
map<pii,int> ind;
X = x;
Y = y;
for(int i = 0; i < N; i++)
ind[{x[i], y[i]}] = i, v[x[i]].pb(y[i]);
vector<pii> edges;
for(int i = 2; i < MAX; i += 2) {
sort(all(v[i]));
for(int k = 0, last = -1; k < sz(v[i]); k++) {
int j = v[i][k];
// olhando o ponto (i,j)
if(last == -1) last = j;
if(k+1 == sz(v[i]) or v[i][k+1] - j != 2) range[i].pb({last, j}), last = -1;
else edges.pb({ind[{i, j}], ind[{i, j+2}]});
}
}
for(int i = 2; i < MAX; i += 2) {
for(int j = 0, k = 0; j < sz(range[i]) and k < sz(range[i-2]); ) {
if(range[i][j].sc < range[i-2][k].fr) j++;
else if(range[i-2][k].sc < range[i][j].fr) k++;
else {
int p = min(range[i][j].sc, range[i-2][k].sc);
edges.pb({ind[{i-2,p}], ind[{i,p}]});
if(range[i][j].sc < range[i-2][k].sc) j++;
else k++;
}
}
}
if(!check(edges)) return 0;
construct(edges);
return 1;
}
