#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>x, y;
int n;
namespace sub1{
int solve(){
vector<int>p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j){
return y[i] < y[j];
});
vector<int>u, v, a, b;
for(int i = 1; i < n; i++){
if(y[p[i]] > y[p[i - 1]] + 2){
return 0;
}
u.push_back(p[i - 1]);
v.push_back(p[i]);
a.push_back(1);
b.push_back(y[p[i]] - 1);
}
build(u, v, a, b);
return 1;
}
}
namespace sub2{
int solve(){
vector<map<int, int>>id(2);
for(int i = 0; i < n; i++){
id[(x[i] - 1) >> 1][y[i]] = i;
}
vector<pair<int, int>>edge;
auto create_edge = [&] (int i, int x, int y){
if(x == 0){
return;
}
auto it = id[x = (x - 1) >> 1].find(y);
if(it != id[x].end()){
edge.push_back(make_pair(i, it->second));
}
};
for(int i = 0; i < n; i++){
create_edge(i, x[i] - 2, y[i]);
create_edge(i, x[i], y[i] - 2);
}
vector<int>lab(n);
iota(lab.begin(), lab.end(), 0);
auto find_set = [&] (int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
};
function<bool(int, int)>merge = [&] (int i, int j){
if((i = find_set(i)) != (j = find_set(j))){
lab[i] = j;
return true;
}
return false;
};
vector<int>u, v, a, b;
for(auto& [i, j] : edge){
if(merge(i, j)){
u.push_back(i);
v.push_back(j);
if(x[i] == x[j]){
a.push_back(x[i] == 2 ? 1 : 5);
b.push_back(max(y[i], y[j]) - 1);
}
else{
a.push_back(3);
b.push_back(y[i] - 1);
}
}
}
if(u.size() != n - 1){
return 0;
}
build(u, v, a, b);
return 1;
}
}
namespace sub3{
int solve(){
vector<map<int, int>>id(3);
for(int i = 0; i < n; i++){
id[(x[i] - 1) >> 1][y[i]] = i;
}
vector<pair<int, int>>edge;
auto create_edge = [&] (int i, int x, int y){
if(x == 0){
return;
}
auto it = id[x = (x - 1) >> 1].find(y);
if(it != id[x].end()){
edge.push_back(make_pair(i, it->second));
}
};
for(int i = 0; i < n; i++){
create_edge(i, x[i] - 2, y[i]);
create_edge(i, x[i], y[i] - 2);
}
vector<int>lab(n);
iota(lab.begin(), lab.end(), 0);
auto find_set = [&] (int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
};
function<bool(int, int)>merge = [&] (int i, int j){
if((i = find_set(i)) != (j = find_set(j))){
lab[i] = j;
return true;
}
return false;
};
vector<int>u, v, a, b;
sort(edge.begin(), edge.end(), [&] (pair<int, int>i, pair<int, int>j){
return min(make_pair(x[i.first], y[i.first]), make_pair(x[i.second], y[i.second])) < min(make_pair(x[j.first], y[j.first]), make_pair(x[j.second], y[j.second]));
});
map<pair<int, int>, bool>vis;
for(auto& [i, j] : edge){
if(merge(i, j)){
u.push_back(i);
v.push_back(j);
if(x[i] == x[j]){
if(x[i] == 2 || x[i] == 6){
a.push_back(x[i] == 2 ? 1 : 7);
}
else if(!vis[make_pair(3, max(y[i], y[j]) - 1)]){
vis[make_pair(3, max(y[i], y[j]) - 1)] = true;
a.push_back(3);
}
else{
vis[make_pair(5, max(y[i], y[j]) - 1)] = true;
a.push_back(5);
}
b.push_back(max(y[i], y[j]) - 1);
}
else{
int X = max(x[i], x[j]) - 1;
a.push_back(X);
if(!vis[make_pair(X, y[i] - 1)]){
vis[make_pair(X, y[i] - 1)] = true;
b.push_back(y[i] - 1);
}
else{
vis[make_pair(X, y[i] + 1)] = true;
b.push_back(y[i] + 1);
}
}
}
}
if(u.size() != n - 1){
return 0;
}
build(u, v, a, b);
return 1;
}
}
namespace sub456{
int solve(){
vector<int>lab(n);
iota(lab.begin(), lab.end(), 0);
auto find_set = [&] (int i){
while(i != lab[i]){
i = lab[i] = lab[lab[i]];
}
return i;
};
function<bool(int, int)>merge = [&] (int i, int j){
if((i = find_set(i)) != (j = find_set(j))){
lab[i] = j;
return true;
}
return false;
};
vector<int>p(n);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&] (int i, int j){
return x[i] < x[j] || (x[i] == x[j] && y[i] < y[j]);
});
map<pair<int, int>, int>id;
for(int i = 0; i < n; i++){
id[make_pair(x[i], y[i])] = i;
}
vector<int>u, v, a, b;
for(int& i : p){
auto it = id.find(make_pair(x[i], y[i] + 2));
if(it != id.end()){
int p = it->second;
if(merge(i, p)){
if(~((x[i] >> 1) + (y[i] >> 1)) & 1){
a.push_back(x[i] - 1);
}
else{
a.push_back(x[i] + 1);
}
b.push_back(y[i] + 1);
u.push_back(i);
v.push_back(p);
}
}
if((it = id.find(make_pair(x[i] + 2, y[i]))) != id.end()){
int p = it->second;
if(find_set(i) != find_set(p)){
if(((x[i] >> 1) + (y[i] >> 1)) & 1){
if(id.find(make_pair(x[i], y[i] - 2)) != id.end() && id.find(make_pair(x[i] + 2, y[i] - 2)) != id.end()){
continue;
}
b.push_back(y[i] - 1);
}
else{
b.push_back(y[i] + 1);
}
a.push_back(x[i] + 1);
u.push_back(i);
v.push_back(p);
merge(i, p);
}
}
}
if(u.size() != n - 1){
return 0;
}
build(u, v, a, b);
return 1;
}
}
int construct_roads(vector<int>_x, vector<int>_y){
swap(x, _x);
swap(y, _y);
n = x.size();
if(*max_element(x.begin(), x.end()) == 2){
return sub1::solve();
}
if(*max_element(x.begin(), x.end()) <= 4){
return sub2::solve();
}
if(*max_element(x.begin(), x.end()) <= 6){
return sub3::solve();
}
return sub456::solve();
}
