给你一棵由 $$$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]$$$,则树可以分为三个路径:
1. $$$3 \rightarrow 1 \rightarrow 5$$$ ($$$3$$$ 顶点的路径),
2. $$$4$$$($$$1$$$ 顶点的路径)。
3. $$$2$$$($$$1$$$ 顶点的路径)。
将根树拆分为 $$$n=5$$$ 的三个路径的示例,树的根 — 节点 $$$3$$$。
输入
输入数据的第一行包含一个整数 $$$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$$$。
输出
对于第一行的每个测试用例,输出一个整数 $$$m$$$ — 可以覆盖树的所有顶点的非相交引导路径的最小数量。
然后打印 $$$m$$$ 包含路径描述的行。在第一个中打印路径的长度,在第二个中打印从上到下的顺序指定该路径的顶点序列。您可以按任何顺序输出路径。
如果有多个答案,则输出其中任何一个。
示例
输入 #1
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
输出 #1
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