考虑 \(d = 2\) 的部分分。相当于只用 \(2\) 次操作把 \(T\) 变成一条链。
不妨设最后变成的是一个 \(1 \sim n\) 的链，如果不是可以把点重编号。
第一次操作考虑以 \(n\) 为根，每次取每个儿子的子树中的最大值为新的根并和原来的根连边，这样会将整棵树具有堆的性质，即父亲的编号比儿子的编号大。
那么第二次操作时因为删完 \(1 \sim i - 1\) 的点后 \(i\) 一定是叶子，所以合法。
实现时发现第一次操作实际上是求点权 Kruskal 重构树，从小到大加点，并查集维护每个点所在子树的根即可。
\(d = 2\) 的部分分给我们启发。考虑若能让 \(S\) 逆操作 \(d - 2\) 次变成一条链，那么整道题就解决了。
考虑增量法，每次把 \(S\) 中的最大度数减 \(1\)。自底向上构造，若当前点的度数为最大度数，那么就断开它和父亲的连边，在子树里面随便找一个还没标记过的叶子，将父亲和这个叶子连边，并标记这个叶子。容易归纳证明每棵子树中未被标记的叶子个数 \(\ge 1\)，所以不会出现所有叶子都被标记的情况。
时间复杂度 \(O(nd \log n)\)。
code
// Problem: P8949 [YsOI2022] 淀粉树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8949
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 200100;
int n, m, p[maxn], q[maxn], tim, fa[maxn];
vector<int> G[maxn], ans[maxn], leaf[maxn];
set<int> S[maxn], T[maxn];
void dfs(int u, int fa, int d) {
ans[d][u] = fa;
bool fl = 1;
for (int v : S[u]) {
if (v == fa) {
continue;
}
fl = 0;
dfs(v, u, d);
if (leaf[u].size() < leaf[v].size()) {
swap(leaf[u], leaf[v]);
}
for (int x : leaf[v]) {
leaf[u].pb(x);
}
vector<int>().swap(leaf[v]);
}
if (fl) {
leaf[u].pb(u);
return;
}
if ((int)T[u].size() == d) {
assert((int)leaf[u].size() >= 2);
int v = leaf[u].back();
leaf[u].pop_back();
T[fa].insert(v);
T[v].insert(fa);
T[fa].erase(u);
T[u].erase(fa);
}
}
void dfs2(int u, int fa, int d) {
ans[d][u] = fa;
p[u] = ++tim;
q[tim] = u;
for (int v : S[u]) {
if (v == fa) {
continue;
}
dfs2(v, u, d);
}
}
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
inline void merge(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
fa[x] = y;
}
}
void solve() {
scanf("%d%d", &n, &m);
if (n == 2) {
puts("1\n0 1");
return;
}
for (int i = 1; i <= m; ++i) {
ans[i] = vector<int>(n + 2);
}
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
G[u].pb(v);
G[v].pb(u);
}
for (int i = 1, u, v; i < n; ++i) {
scanf("%d%d", &u, &v);
S[u].insert(v);
S[v].insert(u);
}
int rt = 0;
for (int i = 1; i <= n; ++i) {
if ((int)S[i].size() == 1) {
rt = i;
break;
}
}
for (int d = m; d >= 3; --d) {
for (int i = 1; i <= n; ++i) {
vector<int>().swap(leaf[i]);
T[i] = S[i];
}
dfs(rt, 0, d);
for (int i = 1; i <= n; ++i) {
S[i] = T[i];
}
}
dfs2(rt, 0, 2);
for (int i = 1; i <= n; ++i) {
fa[i] = i;
}
for (int i = 1; i <= n; ++i) {
for (int j : G[q[i]]) {
j = find(j);
if (p[j] < i) {
ans[1][j] = q[i];
fa[j] = q[i];
}
}
}
printf("%d\n", m);
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
printf("%d%c", ans[i][j], " \n"[j == n]);
}
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}