E. Permutation Routing
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Bobo is given a tree $$$T = (V, E)$$$ of $$$n$$$ vertices, where there is a number $$$p_i$$$ on vertex $$$i$$$ initially, and $$$p_1,p_2,\dots,p_n$$$ is a permutation of $$$1$$$ to $$$n$$$, meaning that all integers from $$$1$$$ to $$$n$$$ appear exactly once in $$$p_1,p_2,\dots,p_n$$$

In each operation, Bobo can select a matching $$$M \subseteq E$$$ ($$$M$$$ is a matching means that no two edges in $$$M$$$ share a common vertex), and for each $$$(u, v) \in M$$$, swap the number on vertex $$$u$$$ and vertex $$$v$$$ (i.e. swap $$$p_u$$$ and $$$p_v$$$).

Bobo wants to use at most $$$3n$$$ operations to make $$$p_i=i$$$ for each $$$1 \le i \le n$$$, can you please help him?

Input

There are multiple test cases. The first line of the input contains an integer $$$T$$$ $$$(T\geq 1)$$$, indicating the number of test cases. For each test case:

The first line contains a single integer $$$n$$$ ($$$1\le n\le 1000$$$) — the number of vertices of the tree.

The second line contains $$$n$$$ integers $$$p_1,p_2,\cdots,p_n$$$ ($$$1 \le p_i \le n$$$, and $$$p$$$ is a permutation of $$$1$$$ to $$$n$$$) — the initial number on vertex $$$i$$$ is $$$p_i$$$.

Then follow $$$n-1$$$ lines, each with integers $$$u, v$$$ ($$$1\le u,v\le n, u\neq v$$$) — meaning that there is an edge between $$$u$$$ and $$$v$$$.

It is guaranteed that the sum of $$$n^2$$$ of all test cases will not exceed $$$10^6$$$.

Output

For each test case: The first line contains a single integer $$$m$$$ ($$$0\le m \le 3n$$$) — the number of operations you used.

Then $$$m$$$ lines follow, where each line starts with an integer $$$0 \le k_i \lt n$$$ — denoting the number of edges in the matching you select in the $$$i$$$-th operation. Then $$$k_i$$$ integers $$$t_{i, 1}, t_{i, 2}, \cdots, t_{i, k_i}$$$ follow, denoting the indexes of edges you select.

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