#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
typedef long long ll;
struct Edge{
int u, v, idx;
Edge(){}
Edge(int u, int v, int idx): u(u), v(v), idx(idx){}
bool operator==(const Edge &r)const{
return idx==r.idx;
}
};
struct dat{
int x, y;
vector<Edge> vec;
dat(){}
dat(int x, int y, vector<Edge> vec): x(x), y(y), vec(vec){}
bool operator<(const dat &r)const{
if(vec.size() != r.vec.size()) return vec.size() < r.vec.size();
return make_pair(x, y) < make_pair(r.x, r.y);
}
};
int xx[]={-1, 1, 0, 0}, yy[]={0, 0, -1, 1};
int n;
pair<int, int> arr[200002];
map<pair<int, int>, int> idx;
int par[200002];
int edgeU[200002], edgeV[200002], edgeCnt;
int edgeA[200002], edgeB[200002];
vector<pair<int, int> > link[200002];
map<pair<int, int>, vector<Edge> > mp;
set<dat> st;
int find(int x){
if(x==par[x]) return x;
return par[x] = find(par[x]);
}
void merge(int x, int y){
x = find(x), y = find(y);
par[y] = x;
}
void dfs(int u){
int x = arr[u].first, y = arr[u].second;
for(int d=0; d<4; d++){
int tx = x+xx[d]+xx[d], ty = y+yy[d]+yy[d];
if(idx.find(make_pair(tx, ty)) == idx.end()) continue;
int tmp = idx[make_pair(tx, ty)];
if(find(u) == find(tmp)) continue;
edgeU[edgeCnt] = u, edgeV[edgeCnt] = tmp;
if(x == tx){
mp[make_pair(x+1, y+yy[d])].push_back(Edge(u, tmp, edgeCnt));
mp[make_pair(x-1, y+yy[d])].push_back(Edge(u, tmp, edgeCnt));
link[edgeCnt].push_back(make_pair(x+1, y+yy[d]));
link[edgeCnt].push_back(make_pair(x-1, y+yy[d]));
}
else{
mp[make_pair(x+xx[d], y+1)].push_back(Edge(u, tmp, edgeCnt));
mp[make_pair(x+xx[d], y-1)].push_back(Edge(u, tmp, edgeCnt));
link[edgeCnt].push_back(make_pair(x+xx[d], y-1));
link[edgeCnt].push_back(make_pair(x+xx[d], y+1));
}
edgeCnt++;
merge(u, tmp);
dfs(tmp);
}
}
int construct_roads(vector<int> x, vector<int> y) {
n = (int)x.size();
for(int i=0; i<n; i++){
arr[i] = make_pair(x[i], y[i]);
par[i] = i;
idx[arr[i]] = i;
}
int start = min_element(arr, arr+n) - arr;
dfs(start);
for(int i=0; i<n; i++){
if(find(i) != find(0)) return 0;
}
for(auto p: mp){
st.insert(dat(p.first.first, p.first.second, p.second));
}
while(!st.empty()){
dat tmp = *st.begin(); st.erase(st.begin());
if(tmp.vec.empty()) continue;
Edge edge = tmp.vec[0];
edgeA[edge.idx] = tmp.x;
edgeB[edge.idx] = tmp.y;
for(auto p: link[edge.idx]){
if(p.first == tmp.x && p.second == tmp.y) continue;
st.erase(dat(p.first, p.second, mp[p]));
auto it = find(mp[p].begin(), mp[p].end(), Edge(edgeU[edge.idx], edgeV[edge.idx], edge.idx));
if(it == mp[p].end()) continue;
mp[p].erase(it);
st.insert(dat(p.first, p.second, mp[p]));
}
}
build(vector<int>(edgeU, edgeU+n-1), vector<int>(edgeV, edgeV+n-1), vector<int>(edgeA, edgeA+n-1), vector<int>(edgeB, edgeB+n-1));
return 1;
}
