#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;
// 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});
}
// Add 1x1 blocks for non-tree edges to satisfy remaining adjacencies
for (int v : fake_children[u]) {
items.push_back({{{v}}, 1, 1, 0, 0});
}
// Base case: leaf node with no non-tree edges needing placement
if (items.empty()) {
return {{u}};
}
// 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 = 2;
for (auto& item : items) {
total_area += (item.w + 1) * (item.h + 1);
max_W = max(max_W, item.w + 2);
}
// Target a roughly square boundary to minimize K
max_W = max(max_W, (int)ceil(sqrt(total_area * 1.5)));
int cx = 1, cy = 1;
int shelf_H = 0;
int max_x = 1, max_y = 1;
// Shelf packing logic to tightly pack children
for (auto& item : items) {
if (cx > 1 && cx + item.w > max_W) {
cx = 1;
cy += shelf_H + 1; // Move to the next shelf
shelf_H = 0;
}
item.x = cx;
item.y = cy;
max_x = max(max_x, cx + item.w);
max_y = max(max_y, cy + item.h);
shelf_H = max(shelf_H, item.h);
cx += item.w + 1; // 1 unit of padding to prevent children from touching
}
int box_H = max_y + 1;
int box_W = max_x + 1;
// Create the parent grid filled with the parent's color
vector<vector<int>> G(box_H, vector<int>(box_W, u));
// Blit the child grids onto the parent grid
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) {
Builder builder;
builder.tree_children.resize(N + 1);
builder.fake_children.resize(N + 1);
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]);
}
// BFS to find a spanning tree
vector<bool> visited(N + 1, false);
vector<int> q;
q.push_back(1);
visited[1] = true;
int head = 0;
vector<pair<int, int>> tree_edges;
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);
tree_edges.push_back({u, v});
tree_edges.push_back({v, u});
q.push_back(v);
}
}
}
// Identify non-tree edges and assign them as "fake children"
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
bool is_tree = false;
for (auto& te : tree_edges) {
if (te.first == u && te.second == v) {
is_tree = true; break;
}
}
if (!is_tree) {
builder.fake_children[u].push_back(v);
}
}
// Build the grid recursively starting from the root (country 1)
vector<vector<int>> map_grid = builder.build(1);
// Expand to make it a perfect K x K square matrix
int max_dim = max((int)map_grid.size(), (int)map_grid[0].size());
vector<vector<int>> final_map(max_dim, vector<int>(max_dim, 1));
for (int i = 0; i < map_grid.size(); ++i) {
for (int j = 0; j < map_grid[0].size(); ++j) {
final_map[i][j] = map_grid[i][j];
}
}
return final_map;
}
