#include "parks.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
#define add push_back
#define len(a) ((int)(a).size())
#define all(a) a.begin(), a.end()
#define pii pair<pair<int, int>, int>
#define fr first.first
#define sc first.second
#define index second
const int N = 2e5 + 5;
int parent[N], sz[N];
bool point[N][2];
void make_set(int v) {
parent[v] = v;
sz[v] = 1;
}
int find_set(int v) {
if (v == parent[v])
return v;
return parent[v] = find_set(parent[v]);
}
void union_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
if (sz[a] < sz[b])
swap(a, b);
parent[b] = a;
sz[a] += sz[b];
}
}
int construct_roads(vector<int> x, vector<int> y) {
if (len(x) == 1) {
build({}, {}, {}, {});
return 1;
}
vector<pii> vec;
for(int i = 0; i < len(x); i++){
vec.add({{x[i], y[i]}, i});
make_set(i);
}
sort(all(vec));
vector<int> u, v, a, b;
int qanak = 1;
for(int i = 1; i < len(vec); i++){
if(vec[i].fr != vec[i - 1].fr) qanak++;
else if(vec[i].sc - vec[i - 1].sc == 2) {
u.add(vec[i - 1].index);
v.add(vec[i].index);
union_sets(vec[i - 1].index, vec[i].index);
}
}
for(int i = 0; i < len(vec); i++) swap(vec[i].fr, vec[i].sc);
sort(all(vec));
// for(int i = 0; i < len(vec); i++){
// cout << vec[i].fr << " " << vec[i].sc << endl;
// }
// cout << "---------" << endl;
for(int i = 1; i < len(vec); i++){
if(vec[i].fr == vec[i - 1].fr && vec[i].sc - vec[i - 1].sc == 2){
if(find_set(vec[i].index) != find_set(vec[i - 1].index)){
u.add(vec[i - 1].index);
v.add(vec[i].index);
union_sets(vec[i - 1].index, vec[i].index);
}
}
}
// for(int i = 0; i < len(u); i++){
// cout << u[i] << " " << v[i] << endl;
// }
for(int i = 1; i < len(x); i++){
if(find_set(i) != find_set(i - 1)){
return 0;
}
}
a.resize(len(u));
b.resize(len(u));
for(int i = 0; i < len(u); i++){
if(x[u[i]] != x[v[i]]){
if(x[u[i]] == 2 || x[v[i]] == 2){
a[i] = 3;
b[i] = y[u[i]] + 1;
point[y[u[i]] + 1][0] = true;
}
continue;
}
if(x[u[i]] == 2){
a[i] = x[u[i]] - 1;
b[i] = min(y[u[i]], y[v[i]]) + 1;
}
if(x[u[i]] == 6){
a[i] = x[u[i]] + 1;
b[i] = min(y[u[i]], y[v[i]]) + 1;
}
}
for(int i = 0; i < len(u); i++){
if(x[u[i]] == x[v[i]] && x[u[i]] == 4){
b[i] = min(y[u[i]], y[v[i]]) + 1;
if(!point[b[i]][0]){
a[i] = x[u[i]] - 1;
}
else {
a[i] = x[u[i]] + 1;
point[b[i]][1] = true;
}
}
}
for(int i = 0; i < len(u); i++){
if(x[u[i]] != x[v[i]] && (x[u[i]] == 6 || x[v[i]] == 6)){
a[i] = 5;
b[i] = y[u[i]] + 1;
if(point[b[i]][1]) b[i] -= 2;
}
}
build(u, v, a, b);
return 1;
}
