P8949 [YsOI2022] Starch Tree

Ysuperman teaches everyone about starch and starch trees.

Ysuperman defines a **rooted tree** $S$ to be a starch tree of a tree $T$ if and only if $S$ satisfies the following two conditions (let $s_i$ denote the set of all vertices in the subtree of $S$ rooted at $i$): 1. $S$ and $T$ have the same number of vertices (assume it is $n$) and are labeled $1\sim n$. 1. For any vertex $i$ in $S$ that has at least one child, and for any child $j$ of $i$, it holds that in $T$, vertex $i$ has a direct edge to at least one vertex in $s_j$. It is easy to see that a tree $T$ may have many starch trees. Now Ysuperman gives you $n$ and two trees $T$ and $S$ with vertices labeled $1\sim n$. Let $d$ be the maximum degree of any vertex in $S$. You need to perform at least one operation and at most $d$ operations. In each operation, replace $T$ with any of its starch trees, so that in the end $T$ becomes $S$. Note that the given $S$ is unrooted. As long as the final edge set of $T$ is the same as that of $S$, we consider that $T$ has become $S$. The input guarantees that at least one solution exists.

The first line contains two integers $n,d$. It is guaranteed that $d$ equals the maximum degree of any vertex in $S$. The next $n-1$ lines each contain two integers $u,v$, indicating that there is an edge between $u$ and $v$ in $T$. It is guaranteed that they form a tree. The next $n-1$ lines each contain two integers $u,v$, indicating that there is an edge between $u$ and $v$ in $S$. It is guaranteed that they form a tree.

For easier checking, Ysuperman asks you to output the answer in the form of rooted trees. The first line of the output contains a positive integer $k(1\le k\le d)$, representing the number of operations you perform. Then output $k$ lines. On the $i$-th line, output $n$ integers describing, after the $i$-th operation, the parent of each vertex $1\sim n$ in the rooted tree that $T$ becomes. The parent of the root is defined to be $0$. **Please ensure that the root you output is the root of the starch tree.**

#### Sample 1 Explanation This is $T$:  This is $S$:  This output performs only one operation on $T$, turning $T$ into the following rooted tree:  This rooted tree is a starch tree of $T$, for the following reasons: 1. For child $1$ of $2$, in $T$, $2$ has a direct edge to $1$ in $s_1=\{1\}$. 2. For child $2$ of $3$, in $T$, $3$ has a direct edge to $1$ in $s_2=\{1,2\}$. 3. For child $4$ of $3$, in $T$, $3$ has a direct edge to $4$ in $s_4=\{4\}$. 4. For child $5$ of $3$, in $T$, $3$ has a direct edge to $5$ in $s_5=\{5\}$. The final rooted tree has the same edges as $S$, so this output will be judged as correct. #### Constraints Subtask $1$ ($20$ points): $n\le 6$. Subtask $2$ ($20$ points): $d=2$. Subtask $3$ ($20$ points): $T$ can be turned into $S$ with only one operation, and $n\le 447$. Subtask $4$ ($20$ points): $n\le 2000$. Subtask $5$ ($20$ points): no special restrictions. For all testdata, $2\le n\le 10^5$, and $d\times n\le 2\times 10^5$. #### Hint The checker for this problem is provided as an attachment. Translated by ChatGPT 5