#include <bits/stdc++.h>
std::vector<std::vector<int>> adj;
std::vector<std::vector<int>> dfs(int u, int p) {
std::vector<std::vector<std::vector<int>>> children;
int max_size = 0, sum_width = 0, num_children = 0;
for (int &i : adj[u]) {
if (i == p) {
continue;
}
children.push_back(dfs(i, u));
max_size = std::max(max_size, int(children.back().size()));
sum_width += children.back()[0].size();
num_children++;
}
if (num_children == 0) {
return {{u}};
}
for (auto &i : children) {
while (i.size() < max_size) {
i.push_back(i.back());
}
}
std::vector ans(max_size + 1, std::vector<int>(sum_width + num_children + 1, u));
int start = 1;
for (auto &ch : children) {
for (int i = 0; i < ch.size(); ++i) {
for (int j = 0; j < ch[i].size(); ++j) {
ans[i + 1][start + j] = ch[i][j];
}
}
start += ch[0].size() + 1;
}
return ans;
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A,
std::vector<int> B) {
adj.resize(N + 1);
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
auto ans = dfs(1, 0);
while (ans.size() != ans[0].size()) {
ans.push_back(ans.back());
}
return ans;
}
