Bobo 拥有一棵包含 $n$ 个顶点的树 $T = (V, E)$，初始时顶点 $i$ 上有一个数字 $p_i$，其中 $p_1, p_2, \dots, p_n$ 是 $1$ 到 $n$ 的一个排列，这意味着 $1$ 到 $n$ 的所有整数在 $p_1, p_2, \dots, p_n$ 中恰好出现一次。

在每次操作中，Bobo 可以选择一个匹配 $M \subseteq E$（匹配意味着 $M$ 中的任意两条边不共享公共顶点），并对于每一条边 $(u, v) \in M$，交换顶点 $u$ 和顶点 $v$ 上的数字（即交换 $p_u$ 和 $p_v$）。

Bobo 希望使用最多 $3n$ 次操作使得对于每个 $1 \le i \le n$ 都有 $p_i = i$，你能帮帮他吗？

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($T \ge 1$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 1000$)，表示树的顶点数。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$，且 $p$ 是 $1$ 到 $n$ 的一个排列)，表示顶点 $i$ 上的初始数字为 $p_i$。

接下来 $n-1$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示 $u$ 和 $v$ 之间存在一条边。

保证所有测试数据的 $n^2$ 之和不超过 $10^6$。

输出格式

对于每组测试数据：第一行包含一个整数 $m$ ($0 \le m \le 3n$)，表示你使用的操作次数。

接下来 $m$ 行，每行以一个整数 $0 \le k_i < n$ 开头，表示你在第 $i$ 次操作中选择的匹配包含的边数。随后是 $k_i$ 个整数 $t_{i,1}, t_{i,2}, \dots, t_{i,k_i}$，表示你选择的边的编号（边的编号按输入顺序从 $1$ 到 $n-1$ 编号）。

样例

输入 1

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

输出 1

4
2 4 3
1 1
1 2
1 4