UOJ Logo Universal Online Judge

UOJ

#387. 【UNR #3】To Do Tree

附件下载 统计

提前上学之后,要做的东西就多了起来,To Do List 直接变成了 To Do Tree。

Mike 现在有 $n$ 个ddl,每星期 Mike 最多能肝 $m$ 个ddl,否则 Mike 会爆肝猝死。而且ddl之间有一些依赖关系,开始第 $i$ 个ddl前必须先做完第 $f_i$ 个ddl($f_i < i$),比如说,叉掉假算法之前必须先写一个靠谱的std。ddl间的依赖关系构成了一颗以 $1$ 号ddl为根的树。

现在Mike想知道他最少需要几星期才能肝完所有的ddl。

注意:每星期所有ddl会在周日晚23:59:59同时被肝完,也就是说,一个星期内不能同时肝第 $f_i$ 个ddl和第 $i$ 个ddl。

输入格式

第一行两个整数 $n, m$。

接下来一行 $n - 1$ 个整数,分别表示 $f_2,f_3,\cdots,f_n$。

输出格式

第一行输出一个整数 $t$,表示最少需要的时间。

接下来 $t$ 行,第 $i$ 行表示第 $i$ 星期 Mike 肝的ddl,其中第一个整数 $s_i$ 表示 Mike 这周肝的ddl个数,接下来 $s_i$ 个整数分别是 Mike 这周肝的ddl标号。相邻两个整数间用空格隔开。行末需要一个空格符。

注意最后一行需要回车符,格式不对将会被判为$0$分。

样例一

input

5 2
1 1 1 2

output

3
1 1 
2 2 3 
2 4 5 

explanation

如果时刻 $2$ 没有肝掉第 $2$ 个ddl,则无法在最短时间内肝完所有ddl。

样例二

见样例数据下载。

样例三

见样例数据下载。

限制与约定

对于所有数据,$n \leq 10^{5}, m \leq n, f_{i} < i$。

子任务分值限制
1$30$$n \leq 10$
2$30$$n \leq 16$
3$6$$m = 1$
4$34$$n \leq 10^{5}$

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载

注意:*.ans 文件中只有一行一个整数,表示最少需要的时间,输出是否合法请自行检验。