[YsOI2022] 淀粉树

Ysuperman 定义一棵**有根树** $S$ 是树 $T$ 的一棵淀粉树当且仅当 $S$ 满足如下两个条件（记 $s_i$ 表示 $S$ 中以 $i$ 为根的子树中所有点构成的点集）： 1. $S$ 与 $T$ 点数相同（不妨设为 $n$）且编号为 $1\sim n$。 1. 对于 $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$。 输入保证存在至少一组解。 ## Input 第一行两个数 $n,d$，保证 $d$ 等于 $S$ 中度数最大的点的度数。 接下来 $n-1$ 行每行两个数 $u,v$ 表示 $T$ 中 $u,v$ 有连边。保证形成一棵树。 接下来 $n-1$ 行每行两个数 $u,v$ 表示 $S$ 中 $u,v$ 有连边。保证形成一棵树。 ## Output 为了方便检验，Ysuperman 需要你按照有根树的形式输出答案。 答案第一行一个正整数 $k(1\le k\le d)$ 表示你进行的操作数。 接下来 $k$ 行第 $i$ 行 $n$ 个整数表示你进行第 $i$ 次操作后 $T$ 变成的有根树中 $1\sim n$ 各个点的父亲编号，根的父亲编号规定为 $0$，**请保证你输出树的根是淀粉树的根**。 [samples] ## Background Ysuperman 教大家淀粉质和淀粉树。 ## Note #### 样例 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。