有一棵 n 个节点的以 1 号点为根的有根树。现在可以对这棵树进行若干次操作,每一次操作可以选择树上的一个点然后删掉连接这个点和它的儿子的所有边。
现在我们想知道对于每一个 k (1≤k≤n),最少需要多少次操作能让图中恰好存在 k 个联通块。
输入格式
第一行输入一个正整数 n。
第二行输入 n−1 个整数 f1,f2,...,fn−1,fi 表示 i+1 号点的父亲,保证 1≤fi≤i。
输出格式
输出 n 个整数,第 i 个数表示 k=i 时的答案,如果无法让图中恰好存在 i 个联通块,则输出 -1
。
样例输入1
6
1 2 1 1 2
样例输出1
0 -1 1 1 -1 2
样例输入输出2
见下发文件。
数据规模
共 10 个测试点。
测试点 1,2,3 满足 n≤20。
测试点 4,5,6 满足 n≤100。
对于所有数据,满足 1≤n≤3000。