#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rng;
struct bpmatch{
vector<int>adj[200100];
int match1[200100],match2[400100],dep[200100];
void AE(int a,int b){
adj[a].push_back(b);
}
int bfs(int n){
queue<int>q;
for(int i=1;i<=n;i++)
if(!match1[i])
q.push(i),
dep[i]=1;
else dep[i]=0;
dep[0]=0;
while(q.size()){
int x=q.front();
q.pop();
if(dep[x]>=dep[0]&&dep[0])
continue;
for(auto i:adj[x])
if(!dep[match2[i]])
dep[match2[i]]=dep[x]+1,
q.push(match2[i]);
}
return dep[0];
}
int dfs(int n){
if(!n)return 1;
for(auto i:adj[n]){
if(dep[match2[i]]==dep[n]+1&&dfs(match2[i]))
return match2[match1[n]=i]=n,1;
}
dep[n]=1e9;
return 0;
}
int matching(int n){
int ans=0;
while(bfs(n))for(int i=1;i<=n;i++)
if(!match1[i]) ans+=dfs(i);
return ans;
}
} G;
map<int,int> pts[200100];
vector<pair<int,int>> tre_edges;
struct dsu{
int par[200100];
int abp(int n){
return par[n]?par[n]=abp(par[n]):n;
}
int merge(int a,int b){
a=abp(a),b=abp(b);
return a-b?par[a]=b:0;
}
} DT;
int Xpos[400100],Ypos[400100];
int construct_roads(std::vector<int> x, std::vector<int> y) {
int n=x.size();
for(int i=0;i<n;i++)
pts[x[i]][y[i]]=i+1;
vector<tuple<int,int,int>>E,pt;
for(int i=0;i<n;i++)
pt.push_back({x[i],y[i],i});
sort(pt.begin(),pt.end());
for(auto[X,Y,i]:pt) {
if(pts[X+2][Y])
E.push_back({i+1,pts[X+2][Y],0});
if(pts[X][Y+2])
E.push_back({i+1,pts[X][Y+2],1});
}
vector<int>u,v,A,B;
int CC=0;
for(auto [i,j,k]:E){
if(DT.merge(i,j)){
u.push_back(i-1);
v.push_back(j-1);
int x1=x[i-1]+1,y1=y[i-1]+1;
int x2=x1,y2=y1;
if(k)x2-=2;
else y2-=2;
if(!pts[x1][y1])
pts[x1][y1]=++CC,
Xpos[CC]=x1,
Ypos[CC]=y1;
if(!pts[x2][y2])
pts[x2][y2]=++CC,
Xpos[CC]=x2,
Ypos[CC]=y2;
G.AE(u.size(),pts[x1][y1]);
G.AE(u.size(),pts[x2][y2]);
}
}
if(u.size()-n+1)return 0;
if(G.matching(n-1)!=n-1)
return 0;
for(int i=1;i<n;i++)
A.push_back(Xpos[G.match1[i]]),
B.push_back(Ypos[G.match1[i]]);
build(u,v,A,B);
return 1;
}
