#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
int dsu[200010],L,R;
vector <int> g[200010],match1,match2,dist;
int prt(int n){
if (dsu[n]==n) return n;
return dsu[n]=prt(dsu[n]);
}
void unn(int u,int v){
dsu[prt(u)]=dsu[prt(v)];
}
map <pair <int,int>,int> mp;
vector <pair <int,int> > vmp;
int gt(int u,int v){
if (mp.find({u,v})==mp.end()){
mp[{u,v}]=mp.size()+1;
vmp.push_back({u,v});
}
return mp[{u,v}];
}
void bfs(){
dist.clear();
for (int i=0; i<L; i++) dist.push_back(-1);
queue <int> q;
for (int i=0; i<L; i++){
if (match1[i]==-1){
dist[i]=0;
q.push(i);
}
}
while (!q.empty()){
int tp=q.front(); q.pop();
for (int i:g[tp]){
if (match2[i]!=-1&&dist[match2[i]]==-1){
dist[match2[i]]=dist[tp]+1;
q.push(match2[i]);
}
}
}
}
int dfs(int cur){
for (int i:g[cur]){
if (match2[i]==-1){
match1[cur]=i;
match2[i]=cur;
return 1;
}
}
for (int i:g[cur]){
if (dist[match2[i]]==dist[cur]+1&&dfs(match2[i])){
match1[cur]=i;
match2[i]=cur;
return 1;
}
}
return 0;
}
bool cmp(pair <pair <int,int>,int> u,pair <pair <int,int>,int> v){
if (u.first.second!=v.first.second) return u.first.second<v.first.second;
return u.first.first<v.first.first;
}
int construct_roads(vector <int> x,vector <int> y){
int n=x.size();
pair <pair <int,int>,int> a[n];
for (int i=0; i<n; i++) a[i]={{x[i],y[i]},i};
sort(a,a+n);
for (int i=0; i<n; i++) dsu[i]=i;
vector <int> u,v,A,B;
int cnt=0;
vmp.push_back({-1,-1});
for (int i=1; i<n; i++){
if (a[i-1].first.first==a[i].first.first&&a[i-1].first.second+2==a[i].first.second&&prt(a[i-1].second)!=prt(a[i].second)){
u.push_back(a[i-1].second);
v.push_back(a[i].second);
unn(a[i-1].second,a[i].second);
int tp=gt(a[i].first.first-1,a[i].first.second-1);
g[cnt].push_back(tp);
tp=gt(a[i].first.first+1,a[i].first.second-1);
g[cnt].push_back(tp);
cnt++;
}
}
sort(a,a+n,cmp);
for (int i=1; i<n; i++){
if (a[i-1].first.first+2==a[i].first.first&&a[i-1].first.second==a[i].first.second&&prt(a[i-1].second)!=prt(a[i].second)){
u.push_back(a[i-1].second);
v.push_back(a[i].second);
unn(a[i-1].second,a[i].second);
int tp=gt(a[i].first.first-1,a[i].first.second-1);
g[cnt].push_back(tp);
tp=gt(a[i].first.first-1,a[i].first.second+1);
g[cnt].push_back(tp);
cnt++;
}
}
for (int i=1; i<n; i++){
if (prt(a[i].second)!=prt(a[0].second)) return 0;
}
for (int i=0; i<n-1; i++) match1.push_back(-1);
for (int i=0; i<=vmp.size(); i++) match2.push_back(-1);
L=match1.size(); R=match2.size();
while (1){
bfs();
int aug=0;
for (int i=0; i<L; i++){
if (match1[i]==-1) aug+=dfs(i);
}
if (!aug) break;
}
for (int i=0; i<L; i++){
int tp=match1[i];
A.push_back(vmp[tp].first);
B.push_back(vmp[tp].second);
}
build(u,v,A,B);
return 1;
}
