#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>> cons[200001];
int mask_l[200001];
vector<int> u;
vector<int> v;
vector<int> a;
vector<int> b;
struct dsu{
int sz = 0;
vector<int> pr;
int p(int v){
if(pr[v] == v) return v;
return pr[v] = p(pr[v]);
}
bool un(int u,int v){
u = p(u);
v = p(v);
if(u == v) return 0 ;
pr[u] = v;
sz++;
return 1;
}
} D;
struct edge{
int x;
int y;
int type; // 0 - vert, 1 - hor;
int a;
int b;
};
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
D.pr.resize(n);
for (int i = 0; i < n; ++i)
{
D.pr[i] = i;
}
vector<edge> E;
vector<pair<int,pair<int,int>>> x_d;
vector<pair<int,pair<int,int>>> y_d;
for (int i = 0; i < n; ++i)
{
x_d.push_back({x[i],{y[i],i}});
y_d.push_back({y[i],{x[i],i}});
}
sort(x_d.begin(), x_d.end());
sort(y_d.begin(), y_d.end());
for (int i = 1; i < n; ++i)
{
if(x_d[i].first == x_d[i-1].first and x_d[i].second.first-2 == x_d[i-1].second.first){
D.un(x_d[i-1].second.second,x_d[i].second.second);
E.push_back({x_d[i-1].first,x_d[i-1].second.first,0,x_d[i-1].second.second,x_d[i].second.second});
}
}
for (int i = 1; i < n; ++i)
{
if(y_d[i].first == y_d[i-1].first and y_d[i].second.first-2 == y_d[i-1].second.first){
D.un(y_d[i-1].second.second,y_d[i].second.second);
E.push_back({y_d[i-1].second.first,y_d[i-1].first,1,y_d[i-1].second.second,y_d[i].second.second});
}
}
if(D.sz != n-1) return 0;
set<pair<int,int>> lines;
set<pair<int,int>> points;
sort(E.begin(),E.end(),[](auto a,auto b){
if(a.x != b.x) return a.x < b.x;
if(a.type != b.type) return a.type < b.type;
return a.y < b.y;
});
for (int i = 0; i < E.size(); ++i)
{
if(E[i].type == 0) lines.insert({E[i].x,E[i].y});
}
//assert(E.size() <= n-1);
for (int i = 0; i < E.size(); ++i)
{
//cout << E[i].x << " " << E[i].y << " --\n";
if(E[i].type == 0){
if(points.count({E[i].x-1,E[i].y+1}) == 0){
u.push_back(E[i].a);
v.push_back(E[i].b);
a.push_back(E[i].x-1);
b.push_back(E[i].y+1);
points.insert({E[i].x-1,E[i].y+1});
}
else if(points.count({E[i].x+1,E[i].y+1}) == 0){
u.push_back(E[i].a);
v.push_back(E[i].b);
a.push_back(E[i].x+1);
b.push_back(E[i].y+1);
points.insert({E[i].x+1,E[i].y+1});
}
else return 0;
}
else{
int top = 0;
if(points.count({E[i].x+1,E[i].y-1})) top = 1;
else if(points.count({E[i].x+1,E[i].y+1})) top = 2;
if(top == 0 and lines.count({E[i].x+2,E[i].y-2})) top = 1;
if(top == 0 and lines.count({E[i].x+2,E[i].y})) top = 2;
if(top%2 == 0){
u.push_back(E[i].a);
v.push_back(E[i].b);
a.push_back(E[i].x+1);
b.push_back(E[i].y-1);
points.insert({E[i].x+1,E[i].y-1});
}
else{
u.push_back(E[i].a);
v.push_back(E[i].b);
a.push_back(E[i].x+1);
b.push_back(E[i].y+1);
points.insert({E[i].x+1,E[i].y+1});
}
}
}
//if(points.size() != n-1) return 0;
build(u,v,a,b);
return 1;
}
