题目描述

译自 JOI Open 2014 Day1 T3「宇宙海賊 / Space Pirate」

在一个遥远的星系里，有 $N$ 颗高度文明的星球，从 $1$ 到 $N$ 编号。每颗星球都提供一个传送器。每个传送器都有一个固定的目的地。传送器都是单向的。

银河帝国艺术博物馆在星系中的星球上举办艺术展览。现在，展览在 $1$ 号星球举行。下一次展览将在我们从 $1$ 号星球出发，使用传送器 $K$ 次后到达的星球举行。

太空警察发现，一个太空海盗计划偷走博物馆的藏品。太空海盗会侵入传送器系统，修改了星球 $a$ 的传送器的目的地。星球 $a$ 的传送器的目的地将被改为星球 $b$。太空海盗只会侵入一个星球的传送器系统。然而，太空警察无法找到 $a, b$ 的准确值。

为了预测下一次展览的地点，太空警察想知道对于每个 $i$，满足下一次展览将在星球 $i$ 举行的 $(a, b)$ 的对数。由于你是一个优秀的程序员，太空警察请你来帮他们计算这些对数。

给定每个传送器的目的地。对于每个 $i$，计算满足下一次展览将在星球 $i$ 举行的 $(a, b)$ 的对数。

注意：

• 星球 $i$ 的传送器的目的地可能是星球 $i$ 本身。在这种情况下，如果我们从星球 $i$ 出发，多次使用传送器，我们将留在星球 $i$。
• 即使星球 $a$ 的传送器的当前目的地是星球 $b$，太空海盗也可能侵入传送器系统，将目的地改为星球 $b$。在这种情况下，星球 $a$ 的传送器的目的地仍然是星球 $b$；在计算 $(a, b)$ 的对数时，应该包括这样的对。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $K$，表示星系中有 $N$ 颗星球，下一次展览将在我们从 $1$ 号星球出发，使用传送器 $K$ 次后到达的星球举行。

接下来的 $N$ 行中的第 $i\ (1 \leq i \leq N)$ 行包含一个整数 $A_{i}\ (1 \leq A_{i} \leq N)$。表示星球 $i$ 的传送器的当前目的地是星球 $A_{i}$。

输出格式

输出 $N$ 行。第 $i\ (1 \leq i \leq N)$ 行包含一个整数，表示满足下一次展览将在星球 $i$ 举行的 $(a, b)$ 的对数。

5 7
5
1
4
3
2

1
2
3
3
16

每个传送器的目的地如下图所示。

如果 $(a, b)=(1,4)$，那么星球 $1$ 的传送器的目的地将被改写为星球 $4$。每个传送器的目的地将变成如左图所示。如果我们从星球 $1$ 出发，使用传送器 $7$ 次，我们将到达星球 $4$。因此，下一次展览将在星球 $4$ 举行。（我们使用传送器的方式是 $1 \rightarrow 4 \rightarrow 3 \rightarrow 4 \rightarrow$ $3 \rightarrow 4 \rightarrow 3 \rightarrow 4$。）

有三对 $(a, b)$（即 $(1,4),(2,4),(5,3))$）使得下一次展览将在星球 $4$ 举行。每对$(a, b)$ 的下一次展览的地点如下表所示。

$i$	满足下一次展览将在星球 $i$ 举行的 $(a, b)$
$1$	$(1,1)$
$2$	$(1,2),(2,2)$
$3$	$(1,3),(2,3),(5,4)$
$4$	$(1,4),(2,4),(5,3)$
$5$	$(1,5),(2,1),(2,5),(3,1),(3,2),(3,3),(3,4),(3,5),(4,1),(4,2),(4,3),(4,4),(4,5),(5,1),(5,2),(5,5)$

在计算 $(a, b)$ 的对数时，应该计算 $a=b$ 的对。你也应该计算那些传送器的目的地不会改变的 $(a, b)$ 的对。

40 57
9
24
1
28
29
5
9
1
36
5
35
14
14
29
28
34
28
4
34
36
33
11
22
23
10
18
26
33
36
15
37
31
27
16
25
37
6
31
21
31

4
2
1
12
18
9
1
1
15
0
4
0
0
2
0
11
0
12
0
2
0
0
1
0
5
12
13
13
34
0
5
1
15
10
8
1351
36
1
0
1

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 10^5$
• $N \leq K \leq 10^{18}$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$N\leq 100$	$10$
$2$	$N\leq 3000$	$37$
$3$	$A_{i} \neq A_{j}\ (1 \leq i<j \leq N)$	$33$
$4$	无附加限制	$20$