#include "parks.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef long long ll;
int construct_roads(vector<int> x, vector<int> y) {
int n = x.size();
map<ar<int, 2>, int> mm;
for(int i=0;i<n;i++){
swap(x[i], y[i]);
mm[{x[i], y[i]}] = i;
}
vector<ar<int, 2>> e, p;
vector<int> par(n), sz(n, 1);
iota(par.begin(), par.end(), 0);
function<int(int)> f = [&](int x) { return (par[x] == x ? x : par[x] = f(par[x])); };
auto merge = [&](int a, int b){
a = f(a), b = f(b);
if(a == b) return false;
if(sz[a] < sz[b]) swap(a, b);
par[b] = a, sz[a] += sz[b];
return true;
};
for(int i=0;i<n;i++){
if(mm.count({x[i], y[i] - 2})){
int j = mm[{x[i], y[i] - 2}];
if(merge(i, j)){
e.push_back({j, i});
p.push_back({-1, -1});
}
}
}
for(int i=0;i<n;i++){
if(y[i] == 2 || y[i] == 6){
if(mm.count({x[i] - 2, y[i]})){
int j = mm[{x[i] - 2, y[i]}];
if(merge(i, j)){
e.push_back({j, i});
p.push_back({x[i] - 1, y[i] + (x[i] == 2 ? -1 : +1)});
}
}
}
}
for(int i=0;i<n;i++){
if(y[i] == 4){
if(mm.count({x[i] - 2, y[i]})){
int j = mm[{x[i] - 2, y[i]}];
if(merge(i, j)){
e.push_back({j, i});
p.push_back({-1, -1});
}
}
}
}
if(sz[f(0)] != n) return 0;
assert((int)e.size() == n - 1);
par.pop_back();
iota(par.begin(), par.end(), 0);
sort(par.begin(), par.end(), [&](int i, int j){
if(x[e[i][0]] != x[e[j][0]]){
return x[e[i][0]] < x[e[j][0]];
} else {
int a = (x[e[i][0]] != x[e[i][1]]), b = (x[e[j][0]] != x[e[j][1]]);
return a < b;
}
});
mm.clear();
for(auto i : par){
if(~p[i][0]) { assert(!mm.count(p[i])); mm[p[i]]; continue; }
//~ cout<<e[i][0]<<" "<<e[i][1]<<"\n";
if(x[e[i][0]] == x[e[i][1]]){
int Y = (y[e[i][0]] + y[e[i][1]]) / 2;
p[i] = {x[e[i][0]] - 1, Y};
if(mm.count(p[i])){
p[i][0] += 2;
assert(!mm.count(p[i]));
}
mm[p[i]] = 1;
} else {
int X = (x[e[i][0]] + x[e[i][1]]) / 2;
p[i] = {X, y[e[i][0]] + 1};
if(mm.count(p[i])){
p[i][1] -= 2;
assert(!mm.count(p[i]));
}
mm[p[i]] = 1;
}
}
mm.clear();
vector<int> u(n - 1), v(n - 1), A(n - 1), B(n - 1);
for(int i=0;i+1<n;i++){
u[i] = e[i][0], v[i] = e[i][1], A[i] = p[i][0], B[i] = p[i][1];
swap(A[i], B[i]);
}
build(u, v, A, B);
return 1;
}
