CF1675D.Vertical Paths

You are given a rooted tree consisting of $n$ vertices. Vertices are numbered from $1$ to $n$. Any vertex can be the root of a tree.

A tree is a connected undirected graph without cycles. A rooted tree is a tree with a selected vertex, which is called the root.

The tree is specified by an array of parents $p$ containing $n$ numbers: $p_i$ is a parent of the vertex with the index $i$. The parent of a vertex $u$ is a vertex that is the next vertex on the shortest path from $u$ to the root. For example, on the simple path from $5$ to $3$ (the root), the next vertex would be $1$, so the parent of $5$ is $1$.

The root has no parent, so for it, the value of $p_i$ is $i$ (the root is the only vertex for which $p_i=i$).

Find such a set of paths that:

• each vertex belongs to exactly one path, each path can contain one or more vertices;
• in each path each next vertex — is a son of the current vertex (that is, paths always lead down — from parent to son);
• number of paths is minimal.

For example, if $n=5$ and $p=[3, 1, 3, 3, 1]$, then the tree can be divided into three paths:

1. $3 \rightarrow 1 \rightarrow 5$ (path of $3$ vertices),
2. $4$ (path of $1$ vertices).
3. $2$ (path of $1$ vertices).

Example of splitting a root tree into three paths for $n=5$, the root of the tree — node $3$.

你将得到一棵包含 $n$ 个顶点的有根树。顶点编号为 $1$ 到 $n$。任意顶点均可作为树的根。

树是一种无环的连通无向图；有根树则是选定一个顶点作为根的树。

该树由一个长度为 $n$ 的父节点数组 $p$ 给出：$p_i$ 表示编号为 $i$ 的顶点的父节点。顶点 $u$ 的父节点，是指从 $u$ 到根的最短路径上紧邻 $u$ 的下一个顶点。例如，在从 $5$ 到 $3$（根）的简单路径上，紧邻 $5$ 的下一个顶点是 $1$，因此 $5$ 的父节点为 $1$。

根节点没有父节点，故对根节点而言，其对应的 $p_i = i$（根节点是唯一满足 $p_i = i$ 的顶点）。

请找出一组路径，使得：

• 每个顶点恰好属于一条路径，每条路径可包含一个或多个顶点；
• 在每条路径中，每个后续顶点均为当前顶点的一个子节点（即所有路径均严格向下延伸——从父节点指向子节点）；
• 路径总数最小。

例如，若 $n=5$ 且 $p=[3, 1, 3, 3, 1]$，则该树可被划分为三条路径：

1. $3 \rightarrow 1 \rightarrow 5$（含 $3$ 个顶点的路径），
2. $4$（含 $1$ 个顶点的路径），
3. $2$（含 $1$ 个顶点的路径）。

将一棵以节点 $3$ 为根的有根树划分为三条路径的示例（$n=5$）。

The first line of input data contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the test.

Each test case consists of two lines.

The first of them contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$). It is the number of vertices in the tree.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$). It is guaranteed that the $p$ array encodes some rooted tree.

It is guaranteed that the sum of the values $n$ over all test cases in the test does not exceed $2 \cdot 10^5$.

输入数据的第一行包含一个整数 $t$（$1 \le t \le 10^4$）——表示测试用例的数量。

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

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示树中顶点的数量。

第二行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）。保证数组 $p$ 编码了一棵有根树。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case on the first line, output an integer $m$ — the minimum number of non-intersecting leading down paths that can cover all vertices of the tree.

Then print $m$ pairs of lines containing path descriptions. In the first of them print the length of the path, in the second — the sequence of vertices specifying that path in the order from top to bottom. You can output the paths in any order.

If there are several answers, output any of them.

对于每个测试用例，在第一行输出一个整数 $m$ —— 覆盖树中所有顶点所需的互不相交的“自上而下”路径的最小数目。

然后输出 $m$ 对行，每对行描述一条路径：第一行输出该路径的长度，第二行输出该路径所经过的顶点序列（按从上到下的顺序）。你可以以任意顺序输出这些路径。

如果存在多个合法答案，输出其中任意一个即可。