#include <bits/stdc++.h>
using namespace std;
static inline long long keyEdge(int a, int b) {
if (a > b) swap(a, b);
return (long long)a * 1000LL + b; // N<=40, безопасно
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> adj(N + 1);
vector<vector<char>> g(N + 1, vector<char>(N + 1, 0));
for (int i = 0; i < M; i++) {
int u = A[i], v = B[i];
g[u][v] = g[v][u] = 1;
adj[u].push_back(v);
adj[v].push_back(u);
}
// --- Try find hub h: adjacent to all other vertices ---
int hub = -1;
for (int h = 1; h <= N; h++) {
bool ok = true;
for (int x = 1; x <= N; x++) if (x != h) {
if (!g[h][x]) { ok = false; break; }
}
if (ok) { hub = h; break; }
}
// ---------- CASE A: hub exists -> K = 2N, maximum score ----------
if (hub != -1) {
int K = 2 * N;
vector<vector<int>> C(K, vector<int>(K, hub));
// 1) ensure every color appears at least once
// Place singletons on diagonal-ish safe positions
// Use (2*i, 2*i) for country i (0-indexed -> country i+1)
for (int i = 0; i < N; i++) {
int r = (2 * i) % K;
int c = (2 * i) % K;
C[r][c] = i + 1;
}
// 2) place every edge as a 1x2 domino [u][v] on hub background
// We'll pack edges row by row, leaving at least 1 cell gap.
int r = 0, c = 0;
auto advance_slot = [&]() {
c += 3; // 2 cells + 1 gap
if (c + 1 >= K) { r += 2; c = 0; } // leave row gap too
};
for (int i = 0; i < M; i++) {
int u = A[i], v = B[i];
// find next available slot inside grid
while (r < K && c + 1 < K) {
// avoid overwriting singleton diagonal too often (не критично, но приятно)
// just accept if both cells are currently hub
if (C[r][c] == hub && C[r][c+1] == hub) break;
advance_slot();
}
if (r >= K) break; // theoretically shouldn't happen since K=80 and M<=780, but with spacing can overflow
C[r][c] = u;
C[r][c + 1] = v;
advance_slot();
}
// If some edges didn't fit due to spacing, pack tighter (no gaps) in remaining space
// (Still safe: only touches hub.)
int idx = 0;
// find first not placed? We didn't track; easiest: re-place all edges again but only where hub-hub.
// It is okay if an edge appears multiple times.
for (int i = 0; i < M; i++) {
int u = A[i], v = B[i];
bool placed = false;
for (int rr = 0; rr < K && !placed; rr++) {
for (int cc = 0; cc + 1 < K && !placed; cc++) {
if (C[rr][cc] == hub && C[rr][cc+1] == hub) {
C[rr][cc] = u;
C[rr][cc+1] = v;
placed = true;
}
}
}
// If still not placed, we can't do more; but usually it will place.
}
return C;
}
// ---------- CASE B: fallback (no hub) ----------
// Build a spanning tree (graph must be connected if a map exists).
// Then create a vertical-walk map. K = min(240, 4N).
int K = min(240, 4 * N);
vector<vector<int>> C(K, vector<int>(K, 1));
// BFS to get parent tree
vector<int> parent(N + 1, -1);
queue<int> q;
parent[1] = 0;
q.push(1);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) if (parent[v] == -1) {
parent[v] = u;
q.push(v);
}
}
// If somehow disconnected (shouldn't happen with "map exists"), just paint all 1.
for (int i = 1; i <= N; i++) if (parent[i] == -1) {
// put each color in one cell without any guarantees (but shouldn't happen)
for (int x = 1; x <= N && x < K; x++) C[x][x] = x;
return C;
}
// Build a DFS order list (walk) that uses only tree edges.
vector<vector<int>> tree(N + 1);
for (int v = 2; v <= N; v++) {
tree[parent[v]].push_back(v);
}
vector<int> walk;
function<void(int)> dfs = [&](int u) {
walk.push_back(u);
for (int v : tree[u]) {
dfs(v);
walk.push_back(u);
}
};
dfs(1);
// Ensure walk length <= K, otherwise truncate (still keeps valid adjacencies, but might lose some colors)
// To keep all colors, we first ensure every node appears by adding missing nodes (via parent path).
vector<int> seen(N + 1, 0);
for (int x : walk) seen[x] = 1;
for (int v = 1; v <= N; v++) if (!seen[v]) walk.push_back(v);
if ((int)walk.size() > K) walk.resize(K);
while ((int)walk.size() < K) walk.push_back(walk.back());
// Paint rows as the walk (each row constant).
for (int r = 0; r < K; r++) {
int col = walk[r];
for (int c = 0; c < K; c++) C[r][c] = col;
}
// Now we at least satisfy condition 1 and condition 3 (only adjacencies between consecutive rows).
// Try to realize edges: for each edge (u,v), if we have some row r with C[r]=u and C[r+1]=v (or v/u),
// then edge is already realized via vertical boundary. Otherwise we cannot guarantee within small K without hub.
// (Still should pass many cases; but not guaranteed max score.)
return C;
}
