J. Red Pandatrees
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Red pandas have a special type of pantry: the pantree. Pantrees store food in a tree.

Two hungry red pandas, Oscar and Lura, have a pantree $$$T$$$ with $$$n$$$ nodes. They want to tidy up the pantree, so they are willing to perform the following shuffle procedure any number of times on the whole tree $$$T$$$. With each shuffle procedure, they will create a new rooted tree out of the nodes of the old tree.

  1. Choose any node $$$V$$$ from the original tree $$$T$$$. Create a new tree $$$T_2$$$, with $$$V$$$ as the root.
  2. Remove $$$V$$$ from $$$T$$$, such that the original tree is split into one or more subtrees (or zero subtrees, if $$$V$$$ is the only node in $$$T$$$).
  3. Shuffle each subtree with the same procedure (again choosing any node as the root), then connect all shuffled subtrees' roots back to $$$V$$$ to finish constructing $$$T_2$$$.

After this, Oscar and Lura are left with a final pantree. They want this pantree to be a line tree with a specific ordering of nodes, such that the first element of the ordering is the root of the tree. They are very hungry, so please find the minimum number of shuffle procedures to order the pantree. Please help them!

A line tree is a tree where each vertex has a degree of at most 2. A line tree is said to satisfy some ordering if and only if a depth first search from the root of the tree visits nodes in the specified ordering.

Note that you ALWAYS need at least one operation, since the original tree is not rooted.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

The first line of every test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of nodes within the original tree $$$T$$$.

The next $$$n - 1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) — an edge within the original tree $$$T$$$. The given edges form a tree.

The last line of every test case will contain $$$n$$$ integers — a permutation $$$p$$$, the desired final ordering of the pantree. $$$p_1$$$ should be the root of the pantree, while $$$p_n$$$ should be the tree's only leaf.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For every test case, first output an integer $$$k$$$ — the minimum number of shuffle procedures needed.

On each of the next $$$k$$$ lines, print the shuffle procedure by outputting the order of nodes chosen.

Example
Input
2
5
5 4
1 2
3 4
3 2
1 2 3 4 5
3
1 2
1 3
1 2 3
Output
1
1 2 3 4 5
2
2 3 1
1 2 3