题目描述

给定一个由 $n$ 个节点组成的有根树。节点从 $1$ 到 $n$ 编号。任何节点都可以是树的根节点。

树是一种没有环的连通无向图。有根树是一棵带有选定顶点（根）的树。

树由包含 $n$ 个数字的父节点 $p$ 数组指定：$p_i$ 是索引为 $i$ 的顶点的父节点。顶点 $u$ 的父节点是在 $u$ 到根的最短路径上的下一个顶点。例如，从 $5$ 到 $3$（根）的简单路径上，下一个顶点是 $1$，因此 $5$ 的父节点是 $1$。

根节点没有父节点，因此对于根节点，$p_i$ 的值是 $i$（根节点是 $p_i = i$ 的唯一节点）。

找到这样一组路径：

每个节点恰好属于一个路径，每个路径可以包含一个或多个节点； 在每个路径中，每个下一个节点都是当前节点的子节点（即，路径总是从父节点到子节点）； 路径数最少。

例如，如果 $n=5，p=[3,1,3,3,1]$，那么树可以被划分为三条路径：

$3→1→5$（包含 $3$ 个节点的路径）， $4$（包含 $1$ 个节点的路径）， $2$（包含 $1$ 个节点的路径）。

将具有 $5$ 个节点的根树分成三条路径的示例，树的根为节点 $3$。

输入格式

每组数据的第一行包含一个整数 $t(1≤t≤10^4)$，表示测试用例的数量。

每个测试用例由两行组成。

第一行包含一个整数 $n(1≤n≤2⋅10^5)$，它是树中节点的数量。

第二行包含 $n$ 个整数 $p_1,p_2,…,p_n(1≤p_i≤n)$。保证数组 $p$ 编码了一棵有根树。

保证所有测试用例中 $n$ 值的总和不超过 $2⋅10^5$。

输出格式

对于第一行的每个测试用例，输出一个整数 $m$——可以覆盖树的所有顶点的不相交的向下引导路径的最小数量。

然后打印 $m$ 对行，每对行包含路径描述。在每对行的第一行打印路径的长度，在第二行按照从上到下的顺序指定该路径的顶点序列。您可以按任何顺序输出路径。

如果有多个答案，输出其中任何一个。

测试样例

6
5
3 1 3 3 1
4
1 1 4 1
7
1 1 2 3 4 5 6
1
1
6
4 4 4 4 1 2
4
2 2 2 2

3
3
3 1 5
1
2
1
4

2
2
1 2
2
4 3

1
7
1 2 3 4 5 6 7

1
1
1

3
3
4 1 5
2
2 6
1
3

3
2
2 1
1
3
1
4

样例说明