#include "parks.h"
#include <bits/stdc++.h>
constexpr int X = 6;
constexpr int Y = 2E5;
int pos[X + 1][Y + 1];
int construct_roads(std::vector<int> x_in, std::vector<int> y_in) {
int n = x_in.size();
{
int max = *std::max_element(x_in.begin(), x_in.end());
assert(max <= X);
}
for (int i = 0; i < n; i++) {
pos[x_in[i]][y_in[i]] = i + 1;
}
std::vector<int> v, u;
std::vector<int> a, b;
for (int y = 2; y + 2 <= Y; y += 2) {
if (pos[2][y] != 0 && pos[2][y + 2] != 0) {
v.push_back(pos[2][y]);
u.push_back(pos[2][y + 2]);
a.push_back(1);
b.push_back(y + 1);
}
}
for (int y = 2; y + 2 <= Y; y += 2) {
if (pos[4][y] != 0 && pos[4][y + 2] != 0) {
v.push_back(pos[4][y]);
u.push_back(pos[4][y + 2]);
a.push_back(y % 4 == 0 ? 5 : 3);
b.push_back(y + 1);
pos[a.back()][y + 1] = -1;
}
}
for (int y = 2; y + 2 <= Y; y += 2) {
if (pos[6][y] != 0 && pos[6][y + 2] != 0) {
v.push_back(pos[6][y]);
u.push_back(pos[6][y + 2]);
a.push_back(7);
b.push_back(y + 1);
}
}
for (int y = 2; y <= Y; y += 2) {
if (pos[2][y] != 0 && pos[4][y] != 0) {
if (pos[3][y - 1] != -1) {
v.push_back(pos[2][y]);
u.push_back(pos[4][y]);
a.push_back(3);
b.push_back(y - 1);
pos[3][y - 1] = -1;
}
else if (pos[3][y + 1] != -1) {
v.push_back(pos[2][y]);
u.push_back(pos[4][y]);
a.push_back(3);
b.push_back(y + 1);
pos[3][y + 1] = -1;
}
}
if (pos[4][y] != 0 && pos[6][y] != 0) {
if (pos[5][y - 1] != -1) {
v.push_back(pos[4][y]);
u.push_back(pos[6][y]);
a.push_back(5);
b.push_back(y - 1);
pos[5][y - 1] = -1;
}
else if (pos[5][y + 1] != -1) {
v.push_back(pos[4][y]);
u.push_back(pos[6][y]);
a.push_back(5);
b.push_back(y + 1);
pos[5][y + 1] = -1;
}
}
}
std::vector<std::vector<int>> adj(n + 1);
for (int i = 0; i < v.size(); i++) {
adj[v[i]].push_back(i);
adj[u[i]].push_back(i);
}
std::vector<bool> vis(n + 1);
auto dfs = [&](auto self, int x) -> void {
vis[x] = true;
for (int i : adj[x]) {
int y = v[i] ^ u[i] ^ x;
if (!vis[y]) {
self(self, y);
}
}
};
dfs(dfs, 1);
if (std::count(vis.begin(), vis.end(), true) == n) {
for (int &x : v) x--;
for (int &y : u) y--;
build(v, u, a, b);
return 1;
}
return 0;
}
