#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(2 * N, vector<int>(2 * 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<bool> done(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);
int t = 0;
for (int diag = 0; diag < 4 * N; ++diag) {
if (t >= tour.size()) {
for (int i = max(0, diag - 2 * N + 1); i <= min(diag, 2 * N - 1); ++i) {
int j = diag - i;
ans[i][j] = 1;
}
} else if (!done[tour[t]]) {
for (int d = diag; d < diag + 3; ++d) {
int idx = 0;
for (int i = max(0, d - 2 * N + 1); i <= min(d, 2 * N - 1); ++i) {
int j = d - i;
if (d == diag + 1 && idx < backedge[tour[t]].size()) {
ans[i][j] = backedge[tour[t]][idx++] + 1;
} else {
ans[i][j] = tour[t] + 1;
}
}
}
diag += 2;
done[tour[t]] = true;
} else {
for (int i = max(0, diag - 2 * N + 1); i <= min(diag, 2 * N - 1); ++i) {
int j = diag - i;
ans[i][j] = tour[t] + 1;
}
}
t++;
}
return ans;
}
