#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int N, int M,
vector<int> A, vector<int> B) {
// special case N==1
if (N == 1) {
return {{1}};
}
// build adjacency lists of the input graph
vector<vector<int>> g(N + 1);
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
g[u].push_back(v);
g[v].push_back(u);
}
// ----- spanning tree (BFS from vertex 1) -----
vector<vector<int>> tree_adj(N + 1);
vector<bool> vis(N + 1, false);
queue<int> q;
q.push(1);
vis[1] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) {
if (!vis[v]) {
vis[v] = true;
tree_adj[u].push_back(v);
tree_adj[v].push_back(u);
q.push(v);
}
}
}
// mark tree edges
vector<vector<bool>> in_tree(N + 1, vector<bool>(N + 1, false));
for (int u = 1; u <= N; ++u) {
for (int v : tree_adj[u]) {
if (u < v) {
in_tree[u][v] = in_tree[v][u] = true;
}
}
}
// ----- Euler tour of the tree -----
vector<int> seq;
function<void(int,int)> dfs_euler = [&](int u, int p) {
seq.push_back(u);
for (int v : tree_adj[u]) {
if (v != p) {
dfs_euler(v, u);
seq.push_back(u);
}
}
};
dfs_euler(1, 0); // root at 1
// ----- classify edges -----
vector<vector<int>> extra_from(N + 1); // for source vertices
vector<bool> is_source(N + 1, false);
for (int i = 0; i < M; ++i) {
int u = A[i], v = B[i];
if (!in_tree[u][v]) { // non‑tree edge
int src = min(u, v); // cover it from the smaller vertex
int dst = max(u, v);
extra_from[src].push_back(dst);
is_source[src] = true;
}
}
// ----- prepare rows (starting from the Euler tour) -----
vector<int> rows = seq;
// insert two extra rows for every source vertex, creating a block of three
for (int u = 1; u <= N; ++u) {
if (!is_source[u]) continue;
// check if a block already exists
bool has_block = false;
for (size_t i = 0; i + 2 < rows.size(); ++i) {
if (rows[i] == u && rows[i+1] == u && rows[i+2] == u) {
has_block = true;
break;
}
}
if (has_block) continue;
// otherwise create the block by inserting two copies of u
size_t idx = 0;
while (rows[idx] != u) ++idx; // first occurrence
rows.insert(rows.begin() + idx + 1, u);
rows.insert(rows.begin() + idx + 2, u);
// now rows[idx..idx+2] are u,u,u
}
int K = rows.size();
vector<vector<int>> C(K, vector<int>(K));
// initial fill: every cell in row i gets colour rows[i]
for (int i = 0; i < K; ++i)
for (int j = 0; j < K; ++j)
C[i][j] = rows[i];
// ----- locate the middle row of each block -----
vector<int> mid_row(N + 1, -1);
for (int u = 1; u <= N; ++u) {
if (!is_source[u]) continue;
for (size_t i = 0; i + 2 < rows.size(); ++i) {
if (rows[i] == u && rows[i+1] == u && rows[i+2] == u) {
mid_row[u] = i + 1; // the middle of the three
break;
}
}
// must have been created
}
// ----- create the non‑tree edges by modifying the middle row -----
for (int u = 1; u <= N; ++u) {
if (!is_source[u]) continue;
int mr = mid_row[u];
int col = 0; // use even columns
for (int v : extra_from[u]) {
C[mr][col] = v;
col += 2;
}
}
return C;
}
