BOSS 树

题目信息

时间限制: 1s

空间限制: 1024M

输入文件: boss.in

输出文件: boss.out

题目描述

A 是刺客兄弟会某个年代的传奇刺客，为了探寻 A 的传奇故事，A 的后代 a 借助 Animus 进入了 A 的记忆世界。已知 A 在他的时代刺杀了 $n$ 位圣殿骑士，但是 a 目前只知道 A 第一天刺杀了【圣殿骑士$1$】，而第 $i$ 位圣殿骑士的情报必须通过刺杀圣殿骑士 $f_i$ 来取得（保证 $f_i \leq i-1$）。

a 的精力有限，一天最多只能在 Animus 刺杀 $m$ 位圣殿骑士，并且若 $f_j=i$，无论 $m$ 是多少，a 都不可能在同一天刺杀 $i, j$ 因为 a 必须得离开 Animus 和战友们研究完 $i$ 的情报才能确定 $j$ 的位置。例如，圣殿骑士 $3$ 满足 $f_3 = 1$，a 可以在第一天刺杀【圣殿骑士 $1$】，但是必须在当天结束 Animus，同战友们研究完 $1$ 提供的情报后，才能锁定 $3$ 的位置，在之后的任意一天都可以对 $3$ 展开刺杀任务。

当代的圣殿骑士团依然在追杀刺客兄弟会，a 必须尽快探索完 A 的记忆帮助刺客兄弟会力挽狂澜，那么 a 最少需要多少天才能在 Animus 刺杀所有 $n$ 位圣殿骑士呢？

输入格式

第一行两个整数 $n, m\left(1 \leq n \leq 10^5, 1 \leq m \leq n\right)$。

第二行 $n-1$ 个整数，分别表示 $f_2, f_3, \ldots, f_n$。

输出格式

第一行一个整数 $ans$，表示 a 至少要花费的天数。

接下来一共 $ans$ 行，每行第一个整数 $s_i(s_i\leq m)$ 表示第 $i$ 天刺杀的圣殿骑士数量，接下来 $s_i$ 个整数表示当天刺杀的圣殿骑士们的编号。

样例

样例输入 1

5 2
1 1 1 2

样例输出 1

3
1 1
2 2 3
2 4 5

数据范围与提示

对于所有数据，$1\leq n\leq 10^5, 1\leq m\leq n, 1\leq f_i < i$