#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ll = long long;
using ar2 = array<int,2>;
using ar3 = array<int,3>;
const int mxN = (int)2e5+10;
int n;
struct Edge{
int fa, fb, x, y;
Edge(int a=0, int b=0, int _x=-1, int _y=-1){
fa=a, fb=b, x=_x, y=_y;
}
};
vector<Edge> edges;
vector<ar3> fountains;
template<int SZ> struct DSU{
int p[SZ];
vector<int> comp[SZ];
void init(int n){
for(int i = 0; i < n; i++){
p[i]=i; comp[i].clear();
comp[i].pb(i);
}
}
int findSet(int i){return p[i]==i?i:p[i]=findSet(p[i]);}
bool isSameSet(int i, int j) {return findSet(i)==findSet(j);}
void unionSet(int i, int j){
int x = findSet(i), y = findSet(j);
if(x==y) return;
if(sz(comp[x]) < sz(comp[y])) swap(x,y);
p[y]=x; for(auto u : comp[y]) comp[x].pb(u);
}
int findSz(int i) { return sz(comp[findSet(i)]); }
};
DSU<mxN> dsu;
set<int> usedB;
int construct_roads(vi x, vi y) {
n = sz(x); dsu.init(n);
if (n==1){ build({}, {}, {}, {}); return 1; }
int mnX = *min_element(all(x));
int mxX = *max_element(all(x));
for(int i = 0; i < n; i++){
fountains.pb({x[i],y[i],i});
}
if(mnX==mxX){
sort(all(fountains),[&](ar3 a, ar3 b){ return a[1]<b[1]; });
for(int i = 1; i < sz(fountains); i++){
if(fountains[i][1]-fountains[i-1][1]==2){
auto [x1,y1,a] = fountains[i-1];
auto [x2,y2,b] = fountains[i];
dsu.unionSet(a,b);
edges.pb(Edge(a,b,x1-1,y1+1));
}
}
}
else if(mxX-mnX==2){
sort(all(fountains),[&](ar3 a, ar3 b){
if(a[0]!=b[0]) return a[0]<b[0];
return a[1]<b[1];
});
set<ar2> S; S.clear();
for(int i = sz(fountains)-1; i>=0; i--){
if(fountains[i][0]!=mxX) break;
S.insert({fountains[i][1], fountains[i][2]});
}
for(int i = 1; i < sz(fountains); i++){
if(fountains[i][0]!=fountains[i-1][0]) continue;
if(fountains[i][1]-fountains[i-1][1]==2){
auto [x1,y1,a] = fountains[i-1];
auto [x2,y2,b] = fountains[i];
dsu.unionSet(a,b);
if(x1==mnX) edges.pb(Edge(a,b,x1-1,y1+1));
else edges.pb(Edge(a,b,x1+1,y1+1));
}
}
for(int i = 0; i < sz(fountains); i++){
auto [x1,y1,a] = fountains[i];
if(x1!=mnX) break;
auto itr = S.lower_bound({y1,-1});
if(itr==end(S) or (*itr)[0]!=y1) continue;
int b = (*itr)[1];
dsu.unionSet(a,b);
edges.pb(Edge(a,b,x1+1,y1-1));
}
}
else if(mxX-mnX==4 and 0){ // currently false for now
sort(all(fountains),[&](ar3 a, ar3 b){
if(a[0]!=b[0]) return a[0]<b[0];
return a[1]<b[1];
});
}
else{
}
if(dsu.findSz(0)!=n) return 0;
vi U, V, A, B;
for(auto edge : edges){
U.pb(edge.fa), V.pb(edge.fb);
A.pb(edge.x), B.pb(edge.y);
}
build(U,V,A,B); return 1;
}
