#include "parks.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=2e5+10;
map<pii,int>mp;
vector<int>adj[maxn];
int marc[maxn];
void dfs(int u){
marc[u]++;
for(int viz : adj[u]){
if(marc[viz]) continue;
dfs(viz);
}
}
int construct_roads(vector<int> x, vector<int> y){
int n=x.size();
for(int i=0;i<n;i++) adj[i].clear(), marc[i]=0;
vector<pair<int,pii>>ord;
for(int i=0;i<n;i++) ord.push_back({i,{x[i],y[i]}}), mp[{x[i],y[i]}]=i+1;
auto cmp=[&](pair<int,pii> z, pair<int,pii> w){
if(z.se.fi!=w.se.fi) return z.se.fi<w.se.fi;
if(z.se.se!=w.se.se) return z.se.se<w.se.se;
return z.fi<w.fi;
};
sort(ord.begin(),ord.end(),cmp);
vector<int>u, v, a, b;
for(int i=0;i<n;i++){
if(i>=1&&ord[i-1].se.fi==ord[i].se.fi&&ord[i-1].se.se+2==ord[i].se.se){
u.push_back(ord[i-1].fi); v.push_back(ord[i].fi);
b.push_back((ord[i-1].se.se+ord[i].se.se)/2);
if(ord[i].se.fi==2) a.push_back(ord[i].se.fi-1);
else a.push_back(ord[i].se.fi+1);
}
if(ord[i].se.fi==2){
if(mp[{ord[i].se.fi+2,ord[i].se.se}]){
u.push_back(ord[i].fi); v.push_back(mp[{ord[i].se.fi+2,ord[i].se.se}]-1);
a.push_back(ord[i].se.fi+1); b.push_back(ord[i].se.se+1);
}
}
}
for(int i=0;i<u.size();i++){
// cerr << u[i] << ' ' << v[i] << '\n';
adj[u[i]].push_back(v[i]);
adj[v[i]].push_back(u[i]);
}
dfs(0);
for(int i=0;i<n;i++) if(!marc[i]) return 0;
build(u,v,a,b);
return 1;
}
