#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
int k = 2*n;
vector ans(k, vector<int>(k));
vector<vector<int>> adj(n);
for (int i = 0; i < m; i++) {
int u = --a[i], v = --b[i];
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<vector<array<int, 2>>> diags(2*k-1);
for (int i = 0; i < k; i++) {
for (int j = 0; j < k; j++) {
diags[i+j].push_back({i, j});
}
}
int curd = 0;
auto filld = [&](int x, vector<int> y) {
int dsz = diags[curd].size(), ysz = y.size();
assert(curd < diags.size());
assert(ysz <= dsz);
for (int i = 0; i < dsz; i++) {
auto [a, b] = diags[curd][i];
if (i < ysz) ans[a][b] = y[i]+1;
else ans[a][b] = x+1;
}
curd++;
};
vector<int> d(n, -1);
d[0] = 0;
function<void(int)> dfs = [&](int i) {
vector<int> back;
for (int j : adj[i]) {
if (d[j] != -1) assert(d[j] < d[i]), back.push_back(j);
}
assert(back.size() <= d[i]);
filld(i, {});
filld(i, back);
filld(i, {});
for (int j : adj[i]) {
if (d[j] != -1) continue;
d[j] = d[i] + 1;
dfs(j);
filld(i, {});
}
};
dfs(0);
return ans;
}
