[YsOI2022] 淀粉树
题目背景
Ysuperman 教大家淀粉质和淀粉树。
题目描述
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$。
输入保证存在至少一组解。
输入输出格式
输入格式
第一行两个数 $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$,**请保证你输出树的根是淀粉树的根**。
输入输出样例
输入样例 #1
5 3
1 2
1 3
3 4
3 5
3 2
3 4
3 5
1 2
输出样例 #1
1
2 3 0 3 3
说明
#### 样例 1 解释
这是 $T$:
![](https://cdn.luogu.com.cn/upload/image_hosting/5qlv4q4t.png)
这是 $S$:
![](https://cdn.luogu.com.cn/upload/image_hosting/xoyaon7y.png)
该输出仅对 $T$ 进行了一次操作,即将 $T$ 变成了下面这棵有根树:
![](https://cdn.luogu.com.cn/upload/image_hosting/0kozi468.png)
这棵有根树是 $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。