#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int N = (int)3e5+11;
int p[N];
mt19937 rnd(time(nullptr));
int components;
int get(int x){
return p[x] == x ? x : p[x] = get(p[x]);
}
void union_sets(int a,int b){
a = get(a), b = get(b);
if(a == b) return;
if(rnd()&1) swap(a,b);
p[a] = b;
components--;
return;
}
int construct_roads(std::vector<int> _x, std::vector<int> _y) {
int n = _x.size();
components = n;
for(int i = 0; i < n; i++) p[i] = i;
vector<pair<int,int>> fountains;
map<pair<int,int>,int> id;
for(int i = 0; i < n; i++){
fountains.push_back(make_pair(_x[i],_y[i]));
id[fountains.back()] = i;
}
sort(fountains.begin(),fountains.end());
set<pair<int,int>> fountainPositions(fountains.begin(),fountains.end());
vector<int> g[n];
vector<pair<int,int>> edges;
vector<pair<int,int>> coords;
set<pair<int,int>> benches;
// shuffle(fountains.begin(),fountains.end(),rnd);
for(int mask = 0; mask < 1; mask++){
for(auto&[x,y] : fountains){
for(int i = -2; i <= 2; i += 2){
// if((mask & 1) == 0 && i == 2) continue;
for(int j = -2; j <= 2; j += 2){
// if((mask >> 1 & 1) == 0 && j == 2) continue;
if(abs(i) + abs(j) != 2) continue;
int xn = x + i, yn = y + j;
int id1 = id[make_pair(x,y)];
if(!id.count(make_pair(xn,yn))) continue;
int id2 = id[make_pair(xn,yn)];
if(get(id1) != get(id2)){
edges.push_back(make_pair(id1,id2));
int a,b;
if(x == xn){
int my = (y+yn)/2;
if(!benches.count({x-1,my}))
a = x-1, b = my;
else if(!benches.count({x+1,my}))
a = x+1, b = my;
else continue;
} else {
int mx = (x+xn)/2;
if(!benches.count({mx,y-1}))
a = mx, b = y-1;
else if(!benches.count({mx,y+1}))
a = mx, b = y+1;
else continue;
}
// cerr << "from " << x << " " << y << ", to " << xn << " " << yn << "\n";
// cerr << "a,b: " << a << " " << b << "\n";
coords.push_back(make_pair(a,b));
benches.insert(make_pair(a,b));
union_sets(id1,id2);
}
}
}
}
}
if(components > 1) return 0;
vector<int> x,y,a,b;
for(size_t i = 0; i < edges.size(); i++){
x.push_back(edges[i].first);
y.push_back(edges[i].second);
a.push_back(coords[i].first);
b.push_back(coords[i].second);
}
build(x,y,a,b);
return 1;
}
