#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>> g(n + 1);
vector<int> vis(n + 1);
for (int i = 0; i < m; i++) {
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
auto fill = [&](int d, int v) {
for (int x = 0; x < 2 * n; x++) {
if (d - x >= 0 && d - x < 2 * n) {
ans[x][d - x] = v;
}
}
};
int ptr = 0, timer = 0;
auto Dfs = [&](auto&& self, int v, int pr) -> void {
vis[v] = ++timer;
int idx = ptr + 1;
ptr += 3;
fill(idx - 1, v);
fill(idx, v);
fill(idx + 1, v);
int ptr2 = max(0, idx - 2 * n + 1);
for (int u : g[v]) {
if (!vis[u]) {
self(self, u, v);
fill(ptr, v);
ptr++;
} else if (vis[u] < vis[v]) {
// ancestor in DFS tree
ans[ptr2][idx - ptr2] = u;
ptr2++;
}
}
};
Dfs(Dfs, 1, 0);
while (ptr < 4 * n) {
fill(ptr, 1);
ptr++;
}
return ans;
}
