#include<bits/stdc++.h>
#include "parks.h"
using namespace std;
const int N = 200010;
int n;
vector <int> g[5*N];
vector <pair <int, int>> pt;
vector<pair <int, int>> arestas;
vector <pair <int, int>> pontos[N][2];
map <pair <int, int>, int> ruas;
pair <int, int> inv_ruas[5*N];
int to[5*N];
int cor;
int mark[5*N];
int cnt;
void dfs(int v){
cnt++;
mark[v] = 1;
for(auto x : g[v]){
if(mark[x]) continue;
dfs(x);
}
return;
}
bool kuhn(int v){
for(auto x : g[v]){
if(mark[x] == cor) continue;
mark[x] = cor;
if(to[x] == -1){
to[x] = v;
return true;
}
if(kuhn(v)){
to[x] = v;
return true;
}
}
return false;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
srand(time(0));
n = x.size();
for(int i = 0;i < x.size();i++){
pontos[x[i]][0].push_back({y[i], i});
pontos[y[i]][1].push_back({x[i], i});
pt.push_back({x[i], y[i]});
}
for(int i = 2;i <= N;i += 2){
sort(pontos[i][0].begin(), pontos[i][0].end());
for(int j = 1;j < pontos[i][0].size();j++){
if(pontos[i][0][j].first - pontos[i][0][j-1].first == 2){
arestas.push_back({pontos[i][0][j].second, pontos[i][0][j-1].second});
}
}
}
for(int i = 2;i <= N;i += 2){
sort(pontos[i][1].begin(), pontos[i][1].end());
for(int j = 1;j < pontos[i][1].size();j++){
if(pontos[i][1][j].first - pontos[i][1][j-1].first == 2){
arestas.push_back({pontos[i][1][j].second, pontos[i][1][j-1].second});
}
}
}
int tam1 = arestas.size(), tam2 = 0;
for(int i = 0;i < arestas.size();i++){
auto [a, b] = arestas[i];
auto [p, q] = pt[a];
auto [r, s] = pt[b];
if(p == r){
int a = max(q, s);
if(ruas.find({p-1, a-1}) == ruas.end()){
ruas[{p-1,a-1}] = tam1+tam2;
inv_ruas[ruas[{p-1, a-1}]] = {p-1, a-1};
tam2++;
}
if(ruas.find({p+1, a-1}) == ruas.end()){
ruas[{p+1,a-1}] = tam1+tam2;
inv_ruas[ruas[{p+1, a-1}]] = {p+1, a-1};
tam2++;
}
g[i].push_back(ruas[{p-1, a-1}]);
g[ruas[{p-1, a-1}]].push_back(i);
g[i].push_back(ruas[{p+1, a-1}]);
g[ruas[{p+1, a-1}]].push_back(i);
}
else{
int a = max(p, r);
if(ruas.find({a-1, q-1}) == ruas.end()){
ruas[{a-1,q-1}] = tam1+tam2;
inv_ruas[tam1+tam2] = {a-1, q-1};
tam2++;
}
if(ruas.find({a-1, q+1}) == ruas.end()){
ruas[{a-1,q+1}] = tam1+tam2;
inv_ruas[tam1+tam2] = {a-1, q+1};
tam2++;
}
g[i].push_back(ruas[{a-1, q-1}]);
g[ruas[{a-1, q-1}]].push_back(i);
g[i].push_back(ruas[{a-1, q+1}]);
g[ruas[{a-1, q+1}]].push_back(i);
}
}
vector <int> vertices, complemento;
for(int i = (tam1 < tam2 ? 0 : tam1);i < (tam1 < tam2 ? tam1 : tam1+tam2);i++){
vertices.push_back(i);
}
for(int i = (tam1 >= tam2 ? 0 : tam1);i < (tam1 >= tam2 ? tam1 : tam1+tam2);i++){
complemento.push_back(i);
}
random_shuffle(vertices.begin(), vertices.end());
memset(to, -1, sizeof to);
for(auto v : vertices){
cor++;
kuhn(v);
}
vector <pair <int, int>> matching;
for(auto x : complemento){
if(to[x] == -1) continue;
matching.push_back({min(to[x], x), max(to[x], x)});
}
vector <int> ans[4];
for(int i = 0;i < 5*N;i++)
g[i].clear();
for(auto [a, b] : matching){
pair <int, int> reta = arestas[a];
pair <int, int> q = inv_ruas[b];
ans[0].push_back(reta.first);
ans[1].push_back(reta.second);
ans[2].push_back(q.first);
ans[3].push_back(q.second);
g[reta.first].push_back(reta.second);
g[reta.second].push_back(reta.first);
}
memset(mark, 0, sizeof mark);
dfs(0);
if(cnt != n) return 0;
build(ans[0], ans[1], ans[2], ans[3]);
return 1;
}
