#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;
// 1. Collect real children recursively
for (int v : tree_children_adj[u]) {
build_layout(v);
items.push_back({v, nodes[v].h, nodes[v].w, 0, 0, false});
}
// 2. Collect fake children (non-tree edges)
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;
// 3. Tri-Axis bin packing search (Height, Width, Area)
for (int sort_mode = 0; sort_mode < 3; ++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 {
sort(temp_items.begin(), temp_items.end(), [](const Child& a, const Child& b) {
return (a.h * a.w) > (b.h * b.w) || (a.h * a.w == b.h * b.w && a.h > b.h);
});
}
int total_area = 0;
int max_W_item = 0;
int 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 MATHEMATICAL PRUNING: Prevents TLE on 100-point edge cases
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;
}
}
}
// 4. Apply the absolute optimal 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 {
sort(items.begin(), items.end(), [](const Child& a, const Child& b) {
return (a.h * a.w) > (b.h * b.w) || (a.h * a.w == b.h * b.w && a.h > b.h);
});
}
int cx = 1, cy = 1;
int 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) {
// Blanket color the bounding box in the parent's color to form expected adjacencies
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;
}
}
// Overlay children directly onto global coordinates
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]);
}
int min_K = 1e9;
int best_root = 1;
// Phase 1: Rapid Abstract Simulation (Now running in O(1) packing time)
for (int root = 1; root <= N; ++root) {
MapSolver temp_solver(N);
vector<vector<bool>> is_tree_edge(N + 1, vector<bool>(N + 1, false));
vector<bool> visited(N + 1, false);
vector<int> q;
q.push_back(root);
visited[root] = true;
int head = 0;
while (head < q.size()) {
int u = q[head++];
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
temp_solver.tree_children_adj[u].push_back(v);
is_tree_edge[u][v] = true;
is_tree_edge[v][u] = true;
q.push_back(v);
}
}
}
// Load balance the non-tree edges to prevent regional bloating
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
if (!is_tree_edge[u][v]) {
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: Single-pass Grid Initialization on Best Root
MapSolver final_solver(N);
vector<vector<bool>> is_tree_edge(N + 1, vector<bool>(N + 1, false));
vector<bool> visited(N + 1, false);
vector<int> q;
q.push_back(best_root);
visited[best_root] = true;
int head = 0;
while (head < q.size()) {
int u = q[head++];
for (int v : adj[u]) {
if (!visited[v]) {
visited[v] = true;
final_solver.tree_children_adj[u].push_back(v);
is_tree_edge[u][v] = true;
is_tree_edge[v][u] = true;
q.push_back(v);
}
}
}
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
if (!is_tree_edge[u][v]) {
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);
// Allocate the single required 2D integer matrix dynamically
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));
// Fire the paint recursion!
final_solver.paint_layout(best_root, 0, 0);
return final_solver.final_map_grid;
}
