C. Path of Crows
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ nests in a forest. These nests are connected by $$$n-1$$$ branches, forming a tree structure. From any nest, a crow can reach any other nest by flying along the branches, and there are no cycles.

A wise old crow wants to travel through all nests exactly once. It can fly in a straight path from one nest to the next if there exists a branch between those nests. The crow already decided the exact order in which it wants to visit the nests.

However, the current branch structure may not form a single straight path. To help the crow, you are allowed to carefully rearrange branches.

Your task is to transform the initial tree structure of nests into the desired chain structure using at most $$$n^2$$$ rearrangement operations.

In one rearrangement operation, you can choose three distinct nests $$$a,b,c$$$ such that the branches $$$(a,b)$$$ and $$$(b,c)$$$ exist in the current tree. Then perform the following change:

  • remove the branch $$$(a,b)$$$;
  • add the branch $$$(a,c)$$$.
It can be shown that after each operation the structure remains a tree.
Input

The first line contains an integer $$$t$$$ — the number of test cases.

For each test case:

  • The first line contains an integer $$$n$$$ $$$(2 \le n \le 300)$$$ — the number of nests.
  • The second line contains $$$n$$$ integers $$$p_1,p_2,\dots,p_n$$$ — a permutation of $$$1$$$ to $$$n$$$. It denotes the order in which the wise old crow wants to visit the nests.
  • The next $$$n-1$$$ lines contain two integers $$$u,v$$$ — there is a branch between $$$u$$$ and $$$v$$$.

It is guaranteed that the given branches form a tree structure.

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

Output

For each test case:

  • Print an integer $$$m$$$ $$$(0 \le m \le n^2)$$$ — the number of moves.
  • Then print $$$m$$$ lines, each containing three integers $$$a\ b\ c$$$ describing one move.

Each printed move must be valid at the moment it is applied. After all moves, the remaining branches must create the desired chain structure $$$p_1,p_2,\dots,p_n$$$.

Example
Input
1
4
1 2 3 4
2 1
2 3
2 4
Output
1
4 2 3
Note

Initial branches are $$$(2,1)$$$, $$$(2,3)$$$, $$$(2,4)$$$.

The move $$$[4\; 2\; 3]$$$ removes branch $$$(4,2)$$$ and adds branch $$$(4,3)$$$.

After the move, the branches become $$$(1,2)$$$, $$$(2,3)$$$, $$$(3,4)$$$, which forms the required chain $$$1-2-3-4$$$.