#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 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);
}
// Target a roughly square boundary box
int max_W = max(max_W_item + 2, (int)ceil(sqrt(total_area * 1.15)));
int cx = 1, cy = 1;
int shelf_H = 0;
int max_x = 0, max_y = 0;
// Shelf packing logic guaranteeing exactly 1-cell padding around all items
for (auto& item : items) {
if (cx > 1 && cx + item.w > max_W) {
cx = 1;
cy += shelf_H + 1; // Drop to the next shelf
shelf_H = 0;
}
item.x = cx;
item.y = cy;
max_x = max(max_x, cx + item.w - 1);
max_y = max(max_y, cy + item.h - 1);
shelf_H = max(shelf_H, item.h);
cx += item.w + 1;
}
int box_H = max_y + 2;
int box_W = max_x + 2;
// Create the parent grid filled 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:
// Try building the entire grid using every single node as the BFS root.
// Pick the representation that yields the smallest grid bounding box.
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);
}
}
}
// Identify non-tree edges to convert them into isolated 1-cell adjacencies
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
if (!is_tree_edge[u][v]) {
builder.fake_children[u].push_back(v);
}
}
vector<vector<int>> map_grid = builder.build(root);
int max_dim = max((int)map_grid.size(), (int)map_grid[0].size());
// Take the most optimal map layout globally
if (max_dim < min_K) {
min_K = max_dim;
best_map = map_grid;
best_root = root;
}
}
// Expand symmetrically to yield a perfect square matrix of precisely K x K dimension
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;
}
