← 返回题目列表

Codeforces · 755/F

F. 波兰球和礼品

中文机器翻译题面 查看原题

圣诞节到了!波兰球和他的朋友们将给自己送礼物。总共有 n 个球。每个 Ball 都有一个他应该根据某种排列 p 为某人带来礼物的人,对于所有 i,pi ≠ i。

不幸的是,球非常笨拙。我们之前就知道,其中有 k 个人会忘记带礼物。如果满足以下两个约束,则球号 i 将得到他的礼物:

1.球号我会带来他应该送的礼物。
2. 球 x 使得 px = i 会带来他的礼物。

如果恰好有 k 个球忘记了他们的礼物,那么得不到礼物的孩子的最小和最大可能数量是多少?

输入

输入的第一行包含两个整数 n 和 k (2 ≤ n ≤ 106, 0 ≤ k ≤ n),分别代表 Ball 的数量和忘记带礼物的 Ball 的数量。

第二行包含从 1 到 n 的整数的排列 p,其中 pi 是应该从第 i 个 Ball 获得礼物的 Ball 的索引。对于所有 i,pi ≠ i 成立。

输出

您应该输出两个值 - 按顺序得不到礼物的球的最小和最大可能数量。

示例

输入 #1

5 2
3 4 1 5 2

输出 #1

2 4

输入 #2

10 1
2 3 4 5 6 7 8 9 10 1

输出 #2

2 2

注意

在第一个示例中,如果第三个和第一个球忘记带礼物,它们将是唯一没有收到礼物的球。因此,最小答案是 2。但是,如果第一个球和第二个球忘记带礼物,那么只有第五个球会得到礼物。所以,最大答案是 4。