#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);
for (int i = 0; i < M; i++) {
adj[A[i] - 1].push_back(B[i] - 1);
adj[B[i] - 1].push_back(A[i] - 1);
}
vector<bool> vis(N);
vector<int> size(N);
vector<vector<int>> grid(4 * N, vector<int>(4 * N));
auto get_size = [&](auto &&get_size, int node) -> int {
vis[node] = true;
size[node] = 1;
for (auto x: adj[node])
if (!vis[x])
size[node] += get_size(get_size, x);
return size[node];
};
auto dfs = [&](auto &&dfs, int node, int l, int r, int d) -> void {
for (int i = d; i < 4 * N; i++) {
for (int j = l; j < r; j++) {
grid[i][j] = node;
}
}
vis[node] = true;
vector<int> children;
for (auto x: adj[node])
if (!vis[x])
children.push_back(x);
int cur_l = 0;
for (int i = 0; i < children.size(); i++) {
dfs(dfs, children[i], cur_l, cur_l + 3 * size[children[i]], d + 1);
cur_l += 3 * size[children[i]] + (i ? 1 : 3);
}
};
get_size(get_size, 0);
vis.assign(N, false);
dfs(dfs, 0, 0, 4 * N, 0);
for (auto &row: grid)
for (auto &el: row)
el++;
return grid;
}
