#include <bits/stdc++.h>
std::vector<std::vector<int>> adj;
std::vector<bool> vis;
std::set<std::pair<int, int>> edges;
std::vector<int> depth;
std::vector<std::vector<int>> dfs(int u, int p) {
edges.erase({u, p});
edges.erase({p, u});
vis[u] = true;
std::vector<std::vector<std::vector<int>>> children;
int max_size = 0, sum_width = 0, num_children = 0;
for (int &i : adj[u]) {
if (vis[i]) {
continue;
}
depth[i] = depth[u] + 1;
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}, {u}};
}
for (auto &i : children) {
while (int(i.size()) < max_size) {
i.push_back(i.back());
}
}
std::vector ans(max_size + 2, std::vector<int>(sum_width + num_children + 1, u));
int start = 1;
for (auto &ch : children) {
for (int i = 0; i < int(ch.size()); ++i) {
for (int j = 0; j < int(ch[i].size()); ++j) {
ans[i + 2][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.clear(), vis.clear(), edges.clear(), depth.clear();
adj.resize(N + 1), vis.resize(N + 1), depth.resize(N + 1);
for (int i = 0; i < M; ++i) {
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
edges.insert({A[i], B[i]});
}
auto a = dfs(1, 0);
std::vector<int> upsert_row(N + 1, a.size()), upsert_col(N + 1);
for (int i = 0; i < int(a.size()) - 1; ++i) {
for (int j = 0; j < int(a[i].size()); ++j) {
if (a[i][j] == a[i + 1][j]) {
upsert_row[a[i][j]] = std::min(upsert_row[a[i][j]], i + 1);
}
}
}
for (int i = 1; i <= N; ++i) {
upsert_col[i] = std::find(a[upsert_row[i]].begin(), a[upsert_row[i]].end(), i) - a[upsert_row[i]].begin() + 1;
}
for (auto [src, to] : edges) {
// to will always be an ancestor/child of src due to the dfs tree
if (depth[to] > depth[src]) {
std::swap(src, to);
}
int x = upsert_row[to], y = upsert_col[to];
a[x][y] = src, a[x + 1][y] = to;
upsert_col[to] += 2;
}
if (a.size() <= a[0].size()) {
while (a.size() < a[0].size()) {
a.push_back(a.back());
}
} else {
int old = a[0].size();
for (auto &i : a) {
i.resize(a.size());
for (int j = old; j < int(i.size()); ++j) {
i[j] = i[j - 1];
}
}
}
return a;
}
