#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>> children(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] = 3;
for (auto x: adj[node]) {
if (!vis[x]) {
size[node] += get_size(get_size, x);
children[node].push_back(x);
}
}
size[node] += children[node].size();
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;
int cur_y = 4 * N - 1;
for (auto x: adj[node]) {
grid[cur_y][l + 1] = x;
cur_y -= 2;
}
int cur_l = l + 3;
for (int i = 0; i < children[node].size(); i++) {
dfs(dfs, children[node][i], cur_l, cur_l + size[children[node][i]], d + 1);
cur_l += size[children[node][i]] + 1;
}
};
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;
}
