{"raw_statement":[{"iden":"background","content":"Ysuperman 教大家淀粉质和淀粉树。"},{"iden":"statement","content":"Ysuperman 定义一棵**有根树** $S$ 是树 $T$ 的一棵淀粉树当且仅当 $S$ 满足如下两个条件（记 $s_i$ 表示 $S$ 中以 $i$ 为根的子树中所有点构成的点集）：\n\n1. $S$ 与 $T$ 点数相同（不妨设为 $n$）且编号为 $1\\sim n$。\n1. 对于 $S$ 中任意一个有儿子的点 $i$，对于其任意一个儿子 $j$，满足在 $T$ 中 $i$ 与 $s_j$ 中至少一个点有直接连边。\n\n容易发现一棵树 $T$ 的淀粉树可能有很多棵。\n\nYsuperman 现在给定 $n$ 以及两棵点编号 $1\\sim n$ 的树 $T$ 和树 $S$，设树 $S$ 中度数最大的点的度数为 $d$，TA 需要你进行至少一次且不超过 $d$ 次操作，每次操作把 $T$ 替换成它的任意一棵淀粉树，使得最终 $T$ 变成 $S$。\n\n请注意，这里给定的 $S$ 是没有给定根的，你只需要满足最后 $T$ 的连边情况和 $S$ 相同我们就认为 $T$ 变成了 $S$。\n\n输入保证存在至少一组解。"},{"iden":"input","content":"第一行两个数 $n,d$，保证 $d$ 等于 $S$ 中度数最大的点的度数。\n\n接下来 $n-1$ 行每行两个数 $u,v$ 表示 $T$ 中 $u,v$ 有连边。保证形成一棵树。\n\n接下来 $n-1$ 行每行两个数 $u,v$ 表示 $S$ 中 $u,v$ 有连边。保证形成一棵树。"},{"iden":"output","content":"为了方便检验，Ysuperman 需要你按照有根树的形式输出答案。\n\n答案第一行一个正整数 $k(1\\le k\\le d)$ 表示你进行的操作数。\n\n接下来 $k$ 行第 $i$ 行 $n$ 个整数表示你进行第 $i$ 次操作后 $T$ 变成的有根树中 $1\\sim n$ 各个点的父亲编号，根的父亲编号规定为 $0$，**请保证你输出树的根是淀粉树的根**。"},{"iden":"note","content":"#### 样例 1 解释\n\n这是 $T$：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5qlv4q4t.png)\n\n这是 $S$：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/xoyaon7y.png)\n\n该输出仅对 $T$ 进行了一次操作，即将 $T$ 变成了下面这棵有根树：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/0kozi468.png)\n\n这棵有根树是 $T$ 的一棵淀粉树，理由如下：\n\n1. 对于 $2$ 的儿子 $1$，在 $T$ 中 $2$ 与 $s_1=\\{1\\}$ 中的 $1$ 有直接连边。\n2. 对于 $3$ 的儿子 $2$，在 $T$ 中 $3$ 与 $s_2=\\{1,2\\}$ 中的 $1$ 有直接连边。\n3. 对于 $3$ 的儿子 $4$，在 $T$ 中 $3$ 与 $s_4=\\{4\\}$ 中的 $4$ 有直接连边。\n4. 对于 $3$ 的儿子 $5$，在 $T$ 中 $3$ 与 $s_5=\\{5\\}$ 中的 $5$ 有直接连边。\n\n最终得到的有根树和 $S$ 的连边情况相同，所以这份输出将被判定为正确。\n\n#### 数据范围\n\n子任务 $1$（$20$ 分），满足 $n\\le 6$。\n\n子任务 $2$（$20$ 分），满足 $d=2$。\n\n子任务 $3$（$20$ 分），满足 $T$ 可以只进行一次操作即可变成 $S$ 且 $n\\le 447$。\n\n子任务 $4$（$20$ 分），满足 $n\\le 2000$。\n\n子任务 $5$（$20$ 分），无特殊限制。\n\n对于所有数据，满足 $2\\le n\\le 10^5$，$d\\times n\\le 2\\times 10^5$。\n\n#### 提示\n\n附件下发了本题 checker。"}],"translated_statement":null,"sample_group":[["5 3\n1 2\n1 3\n3 4\n3 5\n3 2\n3 4\n3 5\n1 2","1\n2 3 0 3 3"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}