#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 200010;
vector <int> g[N];
vector <pair <int, int>> x[N];
vector <pair <int, int>> y[N];
map <pair <int, int>, int> mapear[2];
array <int, 4> pontos[4*N];
vector <pair <int, int>> arvore;
vector <pair <int, int>> arestas;
int mark[N];
int tamanho_componente;
void dfs(int v){
mark[v] = 1;
tamanho_componente++;
for(auto x : g[v]){
if(mark[x]) continue;
arvore.push_back({x, v});
dfs(x);
}
return;
}
vector <pair <int,int>> arestas_bipartido;
int kuhn[5*N], used[5*N];
stack <int> marked;
pair <int, int> inverso[2*N];
bool try_kuhn(int v){
if(used[v]) return false;
used[v] = 1;
for(auto x : g[v]){
if(kuhn[x] == -1){
kuhn[x] = v;
return true;
}
else if(try_kuhn(kuhn[x])){
kuhn[x] = v;
return true;
}
}
return false;
}
int construct_roads(std::vector<int> xx, std::vector<int> yy) {
srand(time(0));
int n = xx.size();
for(int i = 0;i < xx.size();i++){
x[xx[i]].push_back({yy[i], i});
y[yy[i]].push_back({xx[i], i});
}
// construir grafo de pontos, sem fontes
for(int i = 2;i < N;i += 2){
sort(x[i].begin(), x[i].end());
for(int j = 1;j < x[i].size();j++){
auto [y1, p1] = x[i][j-1];
auto [y2, p2] = x[i][j];
if(y2-y1 == 2){
arestas.push_back({p1, p2});
mapear[0][arestas.back()] = arestas.size()-1;
pontos[mapear[0][arestas.back()]] = {i, y1, i, y2};
arestas.push_back({p2, p1});
mapear[0][arestas.back()] = arestas.size()-1;
pontos[mapear[0][arestas.back()]] = {i, y1, i, y2};
}
}
}
for(int i = 2;i < N;i += 2){
sort(y[i].begin(), y[i].end());
for(int j = 1;j < y[i].size();j++){
auto [x1, p1] = y[i][j-1];
auto [x2, p2] = y[i][j];
if(x2-x1 == 2){
arestas.push_back({p1, p2});
mapear[0][arestas.back()] = arestas.size()-1;
pontos[mapear[0][arestas.back()]] = {x1, i, x2, i};
arestas.push_back({p2, p1});
mapear[0][arestas.back()] = arestas.size()-1;
pontos[mapear[0][arestas.back()]] = {x1, i, x2, i};
}
}
}
// construir a arvore (acho que sempre da pra montar)
for(auto [a, b] : arestas){
g[a].push_back(b);
}
dfs(0);
if(tamanho_componente != n){
return 0;
}
for(int i = 0;i <= n;i++){
g[i].clear();
}
for(auto [a, b] : arvore){
//cout << a << ' ' << b << '\n';
}
// montar grafo bipartido
vector <int> vertices;
int qtd_vertices = 0, at = 0;
for(auto [a, b] : arvore){
array <int, 4> pt = pontos[mapear[0][{a, b}]];
if(pt[0] == pt[2]){
pair <int, int> p1 = {pt[0]-1, pt[1]+1};
pair <int, int> p2 = {pt[0]+1, pt[1]+1};
if(mapear[1].find(p1) == mapear[1].end()){
mapear[1][p1] = qtd_vertices;
inverso[qtd_vertices] = p1;
qtd_vertices++;
}
if(mapear[1].find(p2) == mapear[1].end()){
mapear[1][p2] = qtd_vertices;
inverso[qtd_vertices] = p2;
qtd_vertices++;
}
arestas_bipartido.push_back({at, mapear[1][p1]});
arestas_bipartido.push_back({at, mapear[1][p2]});
}
else{
pair <int, int> p1 = {pt[0]+1, pt[1]-1};
pair <int, int> p2 = {pt[0]+1, pt[1]+1};
if(mapear[1].find(p1) == mapear[1].end()){
mapear[1][p1] = qtd_vertices;
inverso[qtd_vertices] = p1;
qtd_vertices++;
}
if(mapear[1].find(p2) == mapear[1].end()){
mapear[1][p2] = qtd_vertices;
inverso[qtd_vertices] = p2;
qtd_vertices++;
}
arestas_bipartido.push_back({at, mapear[1][p1]});
arestas_bipartido.push_back({at, mapear[1][p2]});
}
vertices.push_back(at);
at++;
}
int C = arvore.size();
for(auto [a, b] : arestas_bipartido){
b += C;
//cout << a << ' ' << b << '\n';
g[a].push_back(b);
g[b].push_back(a);
}
sort(vertices.begin(), vertices.end());
random_shuffle(vertices.begin(), vertices.end());
memset(mark, 0, sizeof mark);
memset(kuhn, -1, sizeof kuhn);
for(auto v : vertices){
if(mark[v]) continue;
while(!marked.empty()){
auto x = marked.top();
marked.pop();
used[x] = 0;
}
try_kuhn(v);
}
vector <int> res[4];
for(int x = 0;x < qtd_vertices;x++){
int v = kuhn[x+C];
if(v == -1) continue;
res[0].push_back(arvore[v].first);
res[1].push_back(arvore[v].second);
res[2].push_back(inverso[x].first);
res[3].push_back(inverso[x].second);
}
/*
u = pontos1
v = pontos2
a = x da fonte
b = y da fonte
build(u, v, a, b);
*/
build(res[0], res[1], res[2], res[3]);
return 1;
}
