#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>> adj(n+1), ans(2*n, vector<int>(2*n, 0));
for (int i = 0; i < m; i++) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
vector<int> order, vis(n+1, false);
auto dfs = [&](int node, auto& dfs) -> void {
vis[node] = 1;
order.push_back(node);
for (int u : adj[node]) if (!vis[u]) {
dfs(u, dfs);
order.push_back(node);
}
};
dfs(1, dfs);
int curdiag = 0, N = 2*n;
fill(vis.begin(), vis.end(), 0);
vector<int> freediaglen(n+1), freediag(n+1), seen(n+1, 0), diagof(2*N, 0);
for (int node : order) {
if (seen[node]) {
diagof[curdiag] = node;
curdiag++;
} else {
diagof[curdiag] = diagof[curdiag+1] = diagof[curdiag+2] = node;
freediag[node] = curdiag+1;
freediaglen[node] = (freediag[node] <= N-1 ? freediag[node]+1 : 2*N - freediag[node] - 1);
curdiag += 3;
seen[node] = 1;
}
}
while (curdiag < 2*N-2) diagof[curdiag++] = order.back();
vector<int> ind(n), pos(n+1, 0);
iota(ind.begin(), ind.end(), 1);
sort(ind.begin(), ind.end(), [&](int i, int j){return freediaglen[i] < freediaglen[j];});
for (int i = 0; i < n; i++) pos[ind[i]] = i;
for (int node : ind) {
int x, y;
if (freediag[node] <= N-1) {
x = 0, y = freediag[node];
} else {
y = N-1, x = freediag[node] - N + 1;
}
for (int u : adj[node]) if (pos[u] < pos[node]) {
ans[x][y] = u;
x++;
y--;
}
}
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) if (ans[i][j] == 0) ans[i][j] = diagof[i+j];
return ans;
}
