#include <bits/stdc++.h>
using namespace std;
/* Implementation of create_map
Constructs a square map (K x K) satisfying the given adjacency constraints.
The construction works for any connected graph with N <= 40.
*/
vector<vector<int>> create_map(int N, int M,
vector<int> A, vector<int> B) {
// Build adjacency list
vector<vector<int>> adj(N + 1);
for (int i = 0; i < M; ++i) {
int u = A[i];
int v = B[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
// Build a spanning tree (BFS)
int root = 1; // any vertex works (graph is guaranteed to be connected)
vector<int> parent(N + 1, -1);
vector<int> depth(N + 1, 0);
queue<int> q;
parent[root] = 0;
q.push(root);
vector<int> bfs_order;
while (!q.empty()) {
int u = q.front(); q.pop();
bfs_order.push_back(u);
for (int v : adj[u]) if (parent[v] == -1) {
parent[v] = u;
depth[v] = depth[u] + 1;
q.push(v);
}
}
// Children lists of the tree
vector<vector<int>> children(N + 1);
for (int v = 1; v <= N; ++v) {
if (parent[v] > 0) children[parent[v]].push_back(v);
}
// Determine which edges are tree edges; others become "holes"
vector<vector<int>> holes(N + 1);
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
if (parent[u] == v || parent[v] == u) continue; // tree edge
// choose the endpoint nearer to the root as the host for the hole
int host, other;
if (depth[u] < depth[v] ||
(depth[u] == depth[v] && u < v)) {
host = u; other = v;
} else {
host = v; other = u;
}
holes[host].push_back(other);
}
// Width needed to place all holes with a separating cell of the host color
int maxHole = 0;
for (int v = 1; v <= N; ++v) maxHole = max(maxHole, (int)holes[v].size());
int W = 2 * maxHole + 1;
if (W == 0) W = 1; // at least one column
// Helper to create rows
auto makeRow = [&](int col) -> vector<int> {
return vector<int>(W, col);
};
auto makeMiddleRow = [&](int col) -> vector<int> {
vector<int> row(W, col);
for (int i = 0; i < (int)holes[col].size(); ++i) {
int c = 2 * i + 1; // guaranteed < W
row[c] = holes[col][i];
}
return row;
};
vector<vector<int>> rows;
// Depth‑first construction of the map
function<void(int)> dfs = [&](int v) {
// top row of vertex v
rows.push_back(makeRow(v));
// middle row (contains holes)
rows.push_back(makeMiddleRow(v));
// a row of v that will sit before the first child (acts as a separator)
rows.push_back(makeRow(v));
for (int c : children[v]) {
dfs(c); // child's whole block
rows.push_back(makeRow(v)); // separator after this child
}
};
dfs(root);
int R = (int)rows.size();
int K = max(R, W); // final square size
// If we have fewer rows than K, pad with rows of the root color
while ((int)rows.size() < K) rows.push_back(makeRow(root));
// Pad each row to length K using its own primary color (the first element)
for (auto &row : rows) {
int primary = row[0];
while ((int)row.size() < K) row.push_back(primary);
}
// At this point rows.size() == K and each row has K elements.
return rows;
}
