#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> 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);
items.push_back({g, (int)g.size(), (int)g[0].size(), 0, 0});
}
// 2. Build a maximally dense checkerboard grid for all fake children
if (!fake_children[u].empty()) {
int F = fake_children[u].size();
int Wf = max(1, (int)ceil(sqrt(2.0 * F)));
int Hf = max(1, (int)ceil(2.0 * F / Wf));
// Increment height if necessary to ensure sufficient density capacity
while ( ((Wf * Hf + 1) / 2) < F ) {
Hf++;
}
vector<vector<int>> fake_g(Hf, vector<int>(Wf, u));
int f_idx = 0;
for (int r = 0; r < Hf; ++r) {
for (int c = 0; c < Wf; ++c) {
if ((r + c) % 2 == 0 && f_idx < F) {
fake_g[r][c] = fake_children[u][f_idx++];
}
}
}
items.push_back({fake_g, Hf, Wf, 0, 0});
}
// Base case: leaf node with no sub-grids requiring packing
if (items.empty()) {
return {{u}};
}
// 3. Sort items by height descending for shelf bin packing
sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
return 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);
}
// 4. Exhaustive 1D Bounding Box Search
int best_max_dim = 1e9;
int best_area = 1e9;
int opt_max_W = 1;
int min_test = 1;
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) {
// Word-wrap to the next shelf if boundary is breached
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;
}
// Early break pruning: further increases only worsen the bounding box
if (box_W > box_H * 2 && box_W > best_max_dim) {
break;
}
}
// 5. Apply the discovered optimal shelf packing
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;
}
int box_H = final_max_y + 2;
int box_W = final_max_x + 2;
// Create the parent grid populated entirely with the parent's color
vector<vector<int>> G(box_H, vector<int>(box_W, u));
// Embed the child grids seamlessly
for (auto& item : 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;
// Center-of-Tree Optimization
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;
// Construct the BFS spaning tree
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);
}
}
}
// Identify non-tree edges and assign them to the least-burdened parent
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();
// Load-balancing the fake children limits regional bloat
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 to yield a perfect square matrix matching K 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;
}
