4334: 点的路径

内存限制:128 MB 时间限制:2 S 标准输入输出
题目类型:传统 评测方式:Special Judge 上传者:
提交:26 通过:24

题目描述

给你一棵由 n 个顶点组成的有根树。顶点从 1 到 n 编号。

树由包含 n 个数的数组 p 表示,其中第 i 个数表示 i 号点的父节点 pi ,根节点是唯一 pi = i 的点。

找到这样一组路径: 

  • 每个顶点只属于一个路径,每个路径可以包含一个或多个顶点;
  • 在每条路径中,每个下一个顶点——是当前顶点的子节点(即,路径总是向下——从父节点到子节点);
  •  要使得路径数量最少。
例如:如果 n = 5,p = [3, 1, 3, 3, 1],这棵树可以分为三条路径,如下图所示。
  1. 3 -> 1 -> 5
  2. 4
  3. 2

输入格式

输入数据的第一行包含一个整数 t (1 ≤ t ≤ 104) — 测试中的测试用例数。 

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

其中第一个包含整数 n (1 ≤ n ≤ 2⋅105)。 它是树中的顶点数。 

第二行包含 n 个整数 p1, p2, … , pn (1 ≤ pi ≤ n)。 保证 p 数组是一个有根树。 

保证测试中所有测试用例的 n 值之和不超过 2⋅105。

输出格式

对于第一行的每个测试用例,输出一个整数 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