分数: 800 点
问题陈述
有 N 斯努克王国的城镇,编号方便 1 通过 N。 镇 1 是首都。
王国中的每个城镇都有一个 传送器,一种可以立即将人传送到另一个地方的设施。 城镇传送器的目的地 i 是城镇 a_i (1≤a_i≤N)。 可以保证 人们可以通过使用传送器多次从任何城镇到达首都.
King Snuke 喜欢整数 K。 自私的国王想要改变传送器的目的地,以便满足以下条件:
- 从任意城镇出发,准确使用传送器后将到达首都 总共 K 次。
求出为了满足国王的愿望而需要改变目的地的传送器的最小数量。
约束
- 2≤N≤10^5
- 1≤a_i≤N
- 人们可以通过多次使用传送器从任何城镇到达首都。
- 1≤K≤10^9
输入
输入由标准输入按以下格式给出:
N K a_1 a_2 ... a_N
输出
打印为了满足 King Snuke 的愿望而需要更改目的地的传送器的最小数量。
示例输入 1
3 1 2 3 1
示例输出 1
2
将传送器的目的地更改为 a = (1,1,1).
示例输入 2
4 2 1 1 2 2
示例输出 2
0
没有必要改变传送器的目的地,因为国王的愿望已经得到满足。
示例输入 3
8 2 4 1 2 3 1 2 3 4
示例输出 3
3
例如,将传送器的目的地更改为 a = (1,1,2,1,1,2,2,4).