Reconstructing Merging Operations in a Tree

Bessie the cow, after finishing a course in graph algorithms, decided to build a graph visualizer capable of handling rooted trees with distinct node values. However, her visualizer only supports one operation: merging. A merging operation selects any two distinct sibling nodes (i.e. nodes with the same parent) and merges them into a single node. The new node’s value is given by

[ \max(a,b) ]

if the two merged nodes had values (a) and (b), and its children become the union of the children of the two nodes (preserving their order). Unfortunately, after several merging operations the program crashed and the history of operations was lost. Given the original (initial) tree and the final tree obtained after performing a sequence of merging operations, your task is to output one possible valid sequence of merging operations that could have been applied. It is guaranteed that at least one such sequence exists.

Note that the input trees are represented as rooted trees. In our solution we will simulate one particular series of operations. In our construction, at each node we repeatedly merge its children arbitrarily until the number of children equals the final state. For the purpose of this problem we assume that the final tree provided is exactly the result of merging all siblings (i.e. each node ends up with at most one child).

inputFormat

The input begins with an integer (T) ((1 \le T\le 50)), the number of test cases. Then for each test case, the input is given as follows:

1. An integer (n) (the number of nodes in the initial tree).
2. A line with (n) space‐separated integers representing the values of the nodes (nodes are numbered from (1) to (n)).
3. (n-1) lines each containing two integers (u) and (v) representing an edge from node (u) (the parent) to node (v) (the child).
4. An integer (m) (the number of nodes in the final tree).
5. A line with (m) space‐separated integers representing the node values of the final tree.
6. (m-1) lines each containing two integers representing the edges of the final tree (in the same format as above).

Note: Although the final tree is provided as input, you may ignore it in your simulation if you choose a strategy that always merges siblings until only one child remains at every node. It is guaranteed that the sum of (n) over all test cases does not exceed 1000.

outputFormat

For each test case, output a sequence of merging operations that transforms the initial tree into the final tree. The output for each test case begins with an integer (k), the number of merging operations. Then (k) lines follow, each describing an operation with three integers: the value of the parent under which the merge is performed, and the values of the two nodes being merged. In a merge operation, the merged node’s value becomes (\max(a, b)) if (a) and (b) are the values of the two merged nodes.

When multiple valid sequences exist, output any one of them. It is guaranteed that a valid sequence exists for the given input.

sample

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

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