跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0963. PolandBall and Gifts

  • ID: 969
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 位运算
  • 动态规划
  • 贪心
  • 数学
  • 算法思想
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

PolandBall and Gifts

题目描述

F. PolandBall and Gifts
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

It's Christmas time! PolandBall and his friends will be giving themselves gifts. There are n Balls overall. Each Ball has someone for whom he should bring a present according to some permutation p, pi≠i for all i.

Unfortunately, Balls are quite clumsy. We know earlier that exactly k of them will forget to bring their gift. A Ball number i will get his present if the following two constraints will hold:

  1. Ball number i will bring the present he should give.
  2. Ball x such that px=i will bring his present.

What is minimum and maximum possible number of kids who will not get their present if exactly k Balls will forget theirs?

Input

The first line of input contains two integers n and k (2≤n≤106, 0≤k≤n), representing the number of Balls and the number of Balls who will forget to bring their presents.

The second line contains the permutation p of integers from 1 to n, where pi is the index of Ball who should get a gift from the i-th Ball. For all i, pi≠i holds.

Output

You should output two values− minimum and maximum possible number of Balls who will not get their presents, in that order.

Examples
Input
5 2
3 4 1 5 2
Output
2 4
Input
10 1
2 3 4 5 6 7 8 9 10 1
Output
2 2
Note

In the first sample, if the third and the first balls will forget to bring their presents, they will be th only balls not getting a present. Thus the minimum answer is 2. However, if the first ans the second balls will forget to bring their presents, then only the fifth ball will get a present. So, the maximum answer is 4.


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 403 题。保留原作者与原赛事署名。