题目背景

Ysuperman 教大家淀粉质和淀粉树。

题目描述

Ysuperman 定义一棵有根树 $S$ 是树 $T$ 的一棵淀粉树当且仅当 $S$ 满足如下两个条件（记 $s_i$ 表示 $S$ 中以 $i$ 为根的子树中所有点构成的点集）：

1. $S$ 与 $T$ 点数相同（不妨设为 $n$）且编号为 $1\sim n$。
2. 对于 $S$ 中任意一个有儿子的点 $i$，对于其任意一个儿子 $j$，满足在 $T$ 中 $i$ 与 $s_j$ 中至少一个点有直接连边。

容易发现一棵树 $T$ 的淀粉树可能有很多棵。

Ysuperman 现在给定 $n$ 以及两棵点编号 $1\sim n$ 的树 $T$ 和树 $S$，设树 $S$ 中度数最大的点的度数为 $d$，TA 需要你进行至少一次且不超过 $d$ 次操作，每次操作把 $T$ 替换成它的任意一棵淀粉树，使得最终 $T$ 变成 $S$。

请注意，这里给定的 $S$ 是没有给定根的，你只需要满足最后 $T$ 的连边情况和 $S$ 相同我们就认为 $T$ 变成了 $S$。

输入保证存在至少一组解。

输入格式

第一行两个数 $n,d$，保证 $d$ 等于 $S$ 中度数最大的点的度数。

接下来 $n-1$ 行每行两个数 $u,v$ 表示 $T$ 中 $u,v$ 有连边。保证形成一棵树。

接下来 $n-1$ 行每行两个数 $u,v$ 表示 $S$ 中 $u,v$ 有连边。保证形成一棵树。

输出格式

为了方便检验，Ysuperman 需要你按照有根树的形式输出答案。

答案第一行一个正整数 $k(1\le k\le d)$ 表示你进行的操作数。

接下来 $k$ 行第 $i$ 行 $n$ 个整数表示你进行第 $i$ 次操作后 $T$ 变成的有根树中 $1\sim n$ 各个点的父亲编号，根的父亲编号规定为 $0$，请保证你输出树的根是淀粉树的根。

5 3
1 2
1 3
3 4
3 5
3 2
3 4
3 5
1 2

1
2 3 0 3 3

提示

样例 1 解释

这是 $T$：

这是 $S$：

该输出仅对 $T$ 进行了一次操作，即将 $T$ 变成了下面这棵有根树：

这棵有根树是 $T$ 的一棵淀粉树，理由如下：

1. 对于 $2$ 的儿子 $1$，在 $T$ 中 $2$ 与 $s_1=\{1\}$ 中的 $1$ 有直接连边。
2. 对于 $3$ 的儿子 $2$，在 $T$ 中 $3$ 与 $s_2=\{1,2\}$ 中的 $1$ 有直接连边。
3. 对于 $3$ 的儿子 $4$，在 $T$ 中 $3$ 与 $s_4=\{4\}$ 中的 $4$ 有直接连边。
4. 对于 $3$ 的儿子 $5$，在 $T$ 中 $3$ 与 $s_5=\{5\}$ 中的 $5$ 有直接连边。

最终得到的有根树和 $S$ 的连边情况相同，所以这份输出将被判定为正确。

数据范围

子任务 $1$（$20$ 分），满足 $n\le 6$。

子任务 $2$（$20$ 分），满足 $d=2$。

子任务 $3$（$20$ 分），满足 $T$ 可以只进行一次操作即可变成 $S$ 且 $n\le 447$。

子任务 $4$（$20$ 分），满足 $n\le 2000$。

子任务 $5$（$20$ 分），无特殊限制。

对于所有数据，满足 $2\le n\le 10^5$，$d\times n\le 2\times 10^5$。

提示

附件下发了本题 checker。