#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<int>> ans(3 * N, vector<int>(3 * N, 0));
vector<vector<int>> adj(N);
for (int i = 0; i < M; ++i) {
adj[--A[i]].push_back(--B[i]);
adj[B[i]].push_back(A[i]);
}
for (int i = 0; i < N; ++i) {
sort(adj[i].begin(), adj[i].end());
adj[i].erase(unique(adj[i].begin(), adj[i].end()), adj[i].end());
}
vector<bool> visited(N, false);
vector<int> tour;
vector<vector<int>> backedge(N);
auto dfs = [&](int u, auto &&self) -> void {
visited[u] = true;
tour.push_back(u);
for (auto &v: adj[u]) {
if (!visited[v]) {
self(v, self);
tour.push_back(u);
} else {
backedge[u].push_back(v);
}
}
};
dfs(0, dfs);
for (int diag = 0; diag < 6 * N; ++diag) {
int idx = 0;
for (int i = max(0, diag - 3 * N + 1); i <= min(diag, 3 * N - 1); ++i) {
int j = diag - i;
if (diag % 3 == 1 && idx < backedge[tour[diag / 3]].size()) {
ans[i][j] = backedge[tour[diag / 3]][idx++] + 1;
} else {
ans[i][j] = tour[diag / 3] + 1;
}
}
}
return ans;
}
