/**
* __ __ __ __
* \ \ / / \ \ / (_) _____
* \ \ / /_ _\ \ / / _ ___|_ _|
* \ \/ /| | | |\ \/ / | |/ _ \ | |
* \ / | |_| | \ / | | __/ | |
* \/ \__,_| \/ |_|\____||_|
*
* Author: VuViet
* Created: 2025-08-04 22:30
**/
#include <bits/stdc++.h>
using namespace std;
const int N = 50;
typedef vector<int> vi;
int world_map[2 * N][2 * N];
vi adj[N], tree[N];
int vis[N], par[N], sz[N], depth[N];
pair<int, int> pos[N];
void DFS(int node, int prev, int d)
{
vis[node] = sz[node] = 1;
depth[node] = d;
for (int v : adj[node])
{
if (v == prev || vis[v]) continue;
par[v] = node;
tree[node].push_back(v);
tree[v].push_back(node);
DFS(v, node, d + 1);
sz[node] += sz[v];
}
}
void Build(int node, int prev, int l, int r, int level)
{
for (int i = l; i <= r; ++i) {
world_map[level * 2][i] = node;
}
for (int i = l; i <= r; ++i)
if ((i - l) % 2 == 1)
{
world_map[level * 2 + 1][i] = node;
if (level > 0)
world_map[level * 2 - 1][i] = node;
}
pos[node] = {level * 2, l + 1};
for (int child : tree[node])
{
if (child == prev) continue;
++l;
Build(child, node, l, l + sz[child] * 2 - 2, level + 1);
l += sz[child] * 2 - 1;
}
}
vector<vi> create_map(int n, int m, vi a, vi b)
{
vector<vi> res(2 * n - 1, vi(2 * n - 1, 0));
for (int i = 1; i <= n; ++i)
{
adj[i].clear();
tree[i].clear();
vis[i] = 0;
}
for (int i = 0; i < m; ++i)
{
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
DFS(1, 0, 0);
Build(1, 0, 0, 2 * n - 2, 0);
for (int i = 1; i <= n; ++i)
for (int v : adj[i]) {
if (depth[v] > depth[i] && par[v] != i)
{
auto &[x, y] = pos[i];
world_map[x][y] = v;
y += 2;
}
}
for (int i = 0; i < 2 * n - 1; ++i)
for (int j = 0; j < 2 * n - 1; ++j)
if (res[i][j] == 0)
{
if (i > 0) res[i][j] = world_map[i - 1][j];
else res[i][j] = world_map[i][j - 1];
} else res[i][j] = world_map[i][j];
return res;
}
