题目描述

高橋王国には $N$ 個の町があります。 町は $1$ から $N$ まで番号が振られています。 町 $1$ は首都です。

それぞれの町にはテレポーターが $1$ 台ずつ設置されています。 町 $i$ ($1\ <\ =i\ <\ =N$) のテレポーターの転送先は町 $a_i$ ($1\ <\ =a_i\ <\ =N$) です。 どの町から出発しても、テレポーターを何回か使うことで首都へ辿り着けることが保証されます。

高橋王は正の整数 $K$ が好きです。 わがままな高橋王は、いくつかのテレポーターの転送先を変え、次の条件が成り立つようにしたいと思っています。

• どの町から出発しても、テレポーターをちょうど $K$ 回使うと、最終的に首都にいる。

条件が成り立つようにするためには、最少でいくつのテレポーターの転送先を変えればよいかを求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $a_1$ $a_2$ $...$ $a_N$

输出格式

条件が成り立つようにするためには、最少でいくつのテレポーターの転送先を変えればよいかを出力せよ。

题目大意

有 $n$ 个城市，每个城市有一个传送点，都可以传送到唯一的一个城市，保证从任何位置出发经过若干次传送之后能够到达 $1$ 号城市。现在希望修改一些点的目的地，使得从任何一点出发在传送 $K$ 次之后恰好都能到达 $1$ 号城市，求最少要改变目的地的城市的数量。

Translated by @加藤圣教_封仙

3 1
2 3 1

2

4 2
1 1 2 2

0

8 2
4 1 2 3 1 2 3 4

3

提示

制約

• $2\ <\ =N\ <\ =10^5$
• $1\ <\ =a_i\ <\ =N$
• どの町から出発しても、テレポーターを何回か使うことで首都へ辿り着ける。
• $1\ <\ =K\ <\ =10^9$

Sample Explanation 1

テレポーターの転送先を $a\ =\ (1，1，1)$ と変えればよいです。

Sample Explanation 2

最初から条件が成り立っているので、テレポーターの転送先を変える必要はありません。

Sample Explanation 3

例えば、テレポーターの転送先を $a\ =\ (1，1，2，1，1，2，2，4)$ と変えればよいです。