#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
struct Item {
vector<vector<int>> grid;
int h, w, x, y;
};
struct Builder {
vector<vector<int>> tree_children;
vector<vector<int>> fake_children;
vector<vector<int>> build(int u) {
vector<Item> base_items;
// 1. Recursively build grids for all real children in the spanning tree
for (int v : tree_children[u]) {
vector<vector<int>> g = build(v);
base_items.push_back({g, (int)g.size(), (int)g[0].size(), 0, 0});
}
// 2. Liquid Gap-Filling: Treat fake children as individual 1x1 items.
// This allows them to dynamically fill the empty shelf space left by large tree-children.
for (int v : fake_children[u]) {
base_items.push_back({{{v}}, 1, 1, 0, 0});
}
if (base_items.empty()) {
return {{u}};
}
int best_max_dim = 1e9;
int best_area = 1e9;
int opt_max_W = 1;
bool sort_by_height_opt = true;
// 3. Dual-Axis Packing: Try sorting by Height, then by Width
for (int sort_mode = 0; sort_mode < 2; ++sort_mode) {
vector<Item> items = base_items;
if (sort_mode == 0) {
sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
return a.h > b.h || (a.h == b.h && a.w > b.w);
});
} else {
sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
return a.w > b.w || (a.w == b.w && a.h > b.h);
});
}
int total_area = 0;
int max_W_item = 0;
for (auto& item : items) {
total_area += (item.w + 1) * (item.h + 1);
max_W_item = max(max_W_item, item.w);
}
int min_test = max_W_item;
int max_test = total_area + max_W_item + 5;
for (int test_W = min_test; test_W <= max_test; ++test_W) {
int cx = 1, cy = 1;
int shelf_H = 0;
int current_max_x = 0, current_max_y = 0;
for (auto& item : 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;
sort_by_height_opt = (sort_mode == 0);
}
if (box_W > box_H * 2 && box_W > best_max_dim) break;
}
}
// 4. Apply the absolute optimal packing configuration found
vector<Item> final_items = base_items;
if (sort_by_height_opt) {
sort(final_items.begin(), final_items.end(), [](const Item& a, const Item& b) {
return a.h > b.h || (a.h == b.h && a.w > b.w);
});
} else {
sort(final_items.begin(), final_items.end(), [](const Item& a, const Item& b) {
return a.w > b.w || (a.w == 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 : final_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;
}
int box_H = final_max_y + 2;
int box_W = final_max_x + 2;
// Surround with the parent's color to form exactly intended adjacencies
vector<vector<int>> G(box_H, vector<int>(box_W, u));
for (auto& item : final_items) {
for (int i = 0; i < item.h; ++i) {
for (int j = 0; j < item.w; ++j) {
G[item.y + i][item.x + j] = item.grid[i][j];
}
}
}
return G;
}
};
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]);
}
vector<vector<int>> best_map;
int min_K = 1e9;
int best_root = 1;
// Search for the graph's center by rooting the BFS at every possible node.
// This actively minimizes tree depth, strictly bounding the nesting blow-up.
for (int root = 1; root <= N; ++root) {
Builder builder;
builder.tree_children.resize(N + 1);
builder.fake_children.resize(N + 1);
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;
builder.tree_children[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 bloating any single parent box.
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
if (!is_tree_edge[u][v]) {
int cost_u = builder.tree_children[u].size() + builder.fake_children[u].size();
int cost_v = builder.tree_children[v].size() + builder.fake_children[v].size();
if (cost_u <= cost_v) {
builder.fake_children[u].push_back(v);
} else {
builder.fake_children[v].push_back(u);
}
}
}
vector<vector<int>> map_grid = builder.build(root);
int max_dim = max((int)map_grid.size(), (int)map_grid[0].size());
if (max_dim < min_K) {
min_K = max_dim;
best_map = map_grid;
best_root = root;
}
}
// Expand symmetrically into a K x K map layout constraint
int K = max((int)best_map.size(), (int)best_map[0].size());
vector<vector<int>> final_map(K, vector<int>(K, best_root));
for (int i = 0; i < best_map.size(); ++i) {
for (int j = 0; j < best_map[0].size(); ++j) {
final_map[i][j] = best_map[i][j];
}
}
return final_map;
}
