Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

F. PolandBall and Gifts

time limit per test

1.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIt'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*, *p*_{i} ≠ *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:

- Ball number
*i*will bring the present he should give. - Ball
*x*such that*p*_{x}=*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* ≤ 10^{6}, 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 *p*_{i} is the index of Ball who should get a gift from the *i*-th Ball. For all *i*, *p*_{i} ≠ *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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 19:53:36 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|