Background

Ysuperman teaches everyone about starch and starch trees.

Problem Description

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$.
2. 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.

Input Format

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.

Output Format

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.

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

1
2 3 0 3 3

Hint

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