#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
class MapSolver {
public:
struct Child {
int id;
int h, w;
int x, y;
bool is_fake;
};
struct LayoutNode {
int id;
int h, w;
vector<Child> children;
};
vector<LayoutNode> nodes;
vector<vector<int>> tree_children_adj;
vector<vector<int>> fake_children_adj;
vector<vector<int>> final_map_grid;
MapSolver(int N) {
nodes.resize(N + 1);
tree_children_adj.resize(N + 1);
fake_children_adj.resize(N + 1);
}
void build_layout(int u) {
vector<Child> items;
for (int v : tree_children_adj[u]) {
build_layout(v);
items.push_back({v, nodes[v].h, nodes[v].w, 0, 0, false});
}
for (int v : fake_children_adj[u]) {
items.push_back({v, 1, 1, 0, 0, true});
}
if (items.empty()) {
nodes[u].h = 1;
nodes[u].w = 1;
nodes[u].children = items;
nodes[u].id = u;
return;
}
int best_max_dim = 1e9;
int best_area = 1e9;
int opt_max_W = 1;
int opt_sort_mode = 0;
// 4-Axis Heuristic Bin Packing Simulation
for (int sort_mode = 0; sort_mode < 4; ++sort_mode) {
vector<Child> temp_items = items;
if (sort_mode == 0) {
sort(temp_items.begin(), temp_items.end(), [](const Child& a, const Child& b) {
return a.h > b.h || (a.h == b.h && a.w > b.w);
});
} else if (sort_mode == 1) {
sort(temp_items.begin(), temp_items.end(), [](const Child& a, const Child& b) {
return a.w > b.w || (a.w == b.w && a.h > b.h);
});
} else if (sort_mode == 2) {
sort(temp_items.begin(), temp_items.end(), [](const Child& a, const Child& b) {
int a_area = a.h * a.w, b_area = b.h * b.w;
return a_area > b_area || (a_area == b_area && max(a.h, a.w) > max(b.h, b.w));
});
} else {
sort(temp_items.begin(), temp_items.end(), [](const Child& a, const Child& b) {
int a_max = max(a.h, a.w), b_max = max(b.h, b.w);
return a_max > b_max || (a_max == b_max && (a.h * a.w) > (b.h * b.w));
});
}
int total_area = 0, max_W_item = 0, total_W = 0;
for (auto& item : temp_items) {
total_area += (item.w + 1) * (item.h + 1);
max_W_item = max(max_W_item, item.w);
total_W += item.w + 1;
}
int min_test = max_W_item;
int max_test = min(total_area + max_W_item + 5, total_W + 2);
for (int test_W = min_test; test_W <= max_test; ++test_W) {
// Strict Break: Impossible to beat the bounding box minimums past this point
if (test_W > best_max_dim) break;
int cx = 1, cy = 1;
int shelf_H = 0;
int current_max_x = 0, current_max_y = 0;
for (auto& item : temp_items) {
if (cx > 1 && cx + item.w > test_W) {
cx = 1;
cy += shelf_H + 1;
shelf_H = 0;
}
current_max_x = max(current_max_x, cx + item.w - 1);
current_max_y = max(current_max_y, cy + item.h - 1);
shelf_H = max(shelf_H, item.h);
cx += item.w + 1;
}
int box_H = current_max_y + 2;
int box_W = current_max_x + 2;
int max_dim = max(box_H, box_W);
int area = box_H * box_W;
if (max_dim < best_max_dim || (max_dim == best_max_dim && area < best_area)) {
best_max_dim = max_dim;
best_area = area;
opt_max_W = test_W;
opt_sort_mode = sort_mode;
}
}
}
// Apply best layout discovered
if (opt_sort_mode == 0) {
sort(items.begin(), items.end(), [](const Child& a, const Child& b) {
return a.h > b.h || (a.h == b.h && a.w > b.w);
});
} else if (opt_sort_mode == 1) {
sort(items.begin(), items.end(), [](const Child& a, const Child& b) {
return a.w > b.w || (a.w == b.w && a.h > b.h);
});
} else if (opt_sort_mode == 2) {
sort(items.begin(), items.end(), [](const Child& a, const Child& b) {
int a_area = a.h * a.w, b_area = b.h * b.w;
return a_area > b_area || (a_area == b_area && max(a.h, a.w) > max(b.h, b.w));
});
} else {
sort(items.begin(), items.end(), [](const Child& a, const Child& b) {
int a_max = max(a.h, a.w), b_max = max(b.h, b.w);
return a_max > b_max || (a_max == b_max && (a.h * a.w) > (b.h * b.w));
});
}
int cx = 1, cy = 1, shelf_H = 0;
int final_max_x = 0, final_max_y = 0;
for (auto& item : items) {
if (cx > 1 && cx + item.w > opt_max_W) {
cx = 1;
cy += shelf_H + 1;
shelf_H = 0;
}
item.x = cx;
item.y = cy;
final_max_x = max(final_max_x, cx + item.w - 1);
final_max_y = max(final_max_y, cy + item.h - 1);
shelf_H = max(shelf_H, item.h);
cx += item.w + 1;
}
nodes[u].h = final_max_y + 2;
nodes[u].w = final_max_x + 2;
nodes[u].children = items;
nodes[u].id = u;
}
void paint_layout(int u, int abs_x, int abs_y) {
for (int i = 0; i < nodes[u].h; ++i) {
for (int j = 0; j < nodes[u].w; ++j) {
final_map_grid[abs_y + i][abs_x + j] = u;
}
}
for (auto& child : nodes[u].children) {
if (child.is_fake) {
final_map_grid[abs_y + child.y][abs_x + child.x] = child.id;
} else {
paint_layout(child.id, abs_x + child.x, abs_y + child.y);
}
}
}
};
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> adj(N + 1);
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
// 1. FAST DIAMETER GRAPH CENTER O(N+M)
// First BFS to find one end of the diameter
vector<int> dist1(N + 1, -1);
vector<int> q;
q.push_back(1);
dist1[1] = 0;
int head = 0;
int node_A = 1;
while (head < q.size()) {
int u = q[head++];
node_A = u;
for (int v : adj[u]) {
if (dist1[v] == -1) {
dist1[v] = dist1[u] + 1;
q.push_back(v);
}
}
}
// Second BFS to find the other end of the diameter and backtrack the path
vector<int> distA(N + 1, -1);
vector<int> parentA(N + 1, 0);
q.clear();
q.push_back(node_A);
distA[node_A] = 0;
head = 0;
int node_B = node_A;
while (head < q.size()) {
int u = q[head++];
node_B = u;
for (int v : adj[u]) {
if (distA[v] == -1) {
distA[v] = distA[u] + 1;
parentA[v] = u;
q.push_back(v);
}
}
}
vector<int> path;
int curr = node_B;
while (curr != 0) {
path.push_back(curr);
if (curr == node_A) break;
curr = parentA[curr];
}
// Isolate the exact center nodes of the tree layout
vector<int> candidate_roots;
int len = path.size();
candidate_roots.push_back(path[len / 2]);
if (len % 2 == 0) candidate_roots.push_back(path[len / 2 - 1]);
sort(candidate_roots.begin(), candidate_roots.end());
candidate_roots.erase(unique(candidate_roots.begin(), candidate_roots.end()), candidate_roots.end());
int min_K = 1e9;
int best_root = candidate_roots[0];
// Phase 1: Rapid Simulation exclusively on the 1 or 2 true mathematical centers
for (int root : candidate_roots) {
MapSolver temp_solver(N);
vector<int> tree_parent(N + 1, 0); // O(N) memory to stop MLE
vector<bool> visited(N + 1, false);
q.clear();
q.push_back(root);
visited[root] = true;
head = 0;
while (head < q.size()) {
int u = q[head++];
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
tree_parent[v] = u;
temp_solver.tree_children_adj[u].push_back(v);
q.push_back(v);
}
}
}
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
bool is_tree = (tree_parent[u] == v || tree_parent[v] == u);
if (!is_tree) {
int cost_u = temp_solver.tree_children_adj[u].size() + temp_solver.fake_children_adj[u].size();
int cost_v = temp_solver.tree_children_adj[v].size() + temp_solver.fake_children_adj[v].size();
if (cost_u <= cost_v) temp_solver.fake_children_adj[u].push_back(v);
else temp_solver.fake_children_adj[v].push_back(u);
}
}
temp_solver.build_layout(root);
int max_dim = max(temp_solver.nodes[root].h, temp_solver.nodes[root].w);
if (max_dim < min_K) {
min_K = max_dim;
best_root = root;
}
}
// Phase 2: Render grid
MapSolver final_solver(N);
vector<int> tree_parent(N + 1, 0);
vector<bool> visited(N + 1, false);
q.clear();
q.push_back(best_root);
visited[best_root] = true;
head = 0;
while (head < q.size()) {
int u = q[head++];
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
tree_parent[v] = u;
final_solver.tree_children_adj[u].push_back(v);
q.push_back(v);
}
}
}
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
bool is_tree = (tree_parent[u] == v || tree_parent[v] == u);
if (!is_tree) {
int cost_u = final_solver.tree_children_adj[u].size() + final_solver.fake_children_adj[u].size();
int cost_v = final_solver.tree_children_adj[v].size() + final_solver.fake_children_adj[v].size();
if (cost_u <= cost_v) final_solver.fake_children_adj[u].push_back(v);
else final_solver.fake_children_adj[v].push_back(u);
}
}
final_solver.build_layout(best_root);
int K = max(final_solver.nodes[best_root].h, final_solver.nodes[best_root].w);
final_solver.final_map_grid.assign(K, vector<int>(K, best_root));
final_solver.paint_layout(best_root, 0, 0);
return final_solver.final_map_grid;
}
