#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e6 + 10;
int n, m, x, y, a, b, t;
int k, l;
int ans1, ans2;
int p[maxn];
bool vst[maxn], dp[maxn];
int len[maxn], nlen[maxn], dict[maxn];
int lenl[maxn];
int cont;
int main() {
  scanf("%d%d", &n, &k);
  for (long long i = 1; i < n + 1; i++) {
    scanf("%d", &p[i]);
  }
  cont = 0;
  for (long long i = 1; i < n + 1; i++) {
    if (!vst[i]) {
      t = i;
      l = 0;
      while (!vst[t]) {
        vst[t] = 1;
        t = p[t];
        l++;
      }
      len[++cont] = l;
    }
  }
  sort(len + 1, len + cont + 1);
  int k2 = k;
  m = 0;
  for (long long i = 1; i < cont + 1; i++) {
    if ((len[i] >> 1) <= k2) {
      ans2 += (len[i] >> 1) << 1;
      k2 -= len[i] >> 1;
    } else {
      ans2 += k2 << 1;
      k2 = 0;
    }
    if (len[i] & 1) m++;
  }
  ans2 += min(k2, m);
  ans1 = k;
  m = 0;
  for (long long i = 1; i < cont + 1; i++) {
    if (len[i] == len[i - 1])
      nlen[m]++;
    else {
      nlen[++m]++;
      dict[m] = len[i];
    }
  }
  cont = 0;
  for (long long i = 1; i < m + 1; i++)
    for (int j = 1; nlen[i]; j <<= 1) {
      t = min(nlen[i], j);
      lenl[++cont] = dict[i] * t;
      nlen[i] -= t;
    }
  dp[0] = true;
  for (long long i = 1; i < cont + 1; i++) {
    for (long long j = k - lenl[i]; j > -1; j--) {
      if (dp[j]) dp[j + lenl[i]] = true;
    }
  }
  if (!dp[k]) ans1++;
  printf("%d %d\n", ans1, ans2);
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long maxn = 1e6 + 10;
int n, m, x, y, a, b, t;
int k, l;
int ans1, ans2;
int p[maxn];
bool vst[maxn], dp[maxn];
int len[maxn], nlen[maxn], dict[maxn];
int lenl[maxn];
int cont;
int main() {
  scanf("%d%d", &n, &k);
  for (long long i = 1; i < n + 1; i++) {
    scanf("%d", &p[i]);
  }
  cont = 0;
  for (long long i = 1; i < n + 1; i++) {
    if (!vst[i]) {
      t = i;
      l = 0;
      while (!vst[t]) {
        vst[t] = 1;
        t = p[t];
        l++;
      }
      len[++cont] = l;
    }
  }
  sort(len + 1, len + cont + 1);
  int k2 = k;
  m = 0;
  for (long long i = 1; i < cont + 1; i++) {
    if ((len[i] >> 1) <= k2) {
      ans2 += (len[i] >> 1) << 1;
      k2 -= len[i] >> 1;
    } else {
      ans2 += k2 << 1;
      k2 = 0;
    }
    if (len[i] & 1) m++;
  }
  ans2 += min(k2, m);
  ans1 = k;
  m = 0;
  for (long long i = 1; i < cont + 1; i++) {
    if (len[i] == len[i - 1])
      nlen[m]++;
    else {
      nlen[++m]++;
      dict[m] = len[i];
    }
  }
  cont = 0;
  for (long long i = 1; i < m + 1; i++)
    for (int j = 1; nlen[i]; j <<= 1) {
      t = min(nlen[i], j);
      lenl[++cont] = dict[i] * t;
      nlen[i] -= t;
    }
  dp[0] = true;
  for (long long i = 1; i < cont + 1; i++) {
    for (long long j = k - lenl[i]; j > -1; j--) {
      if (dp[j]) dp[j + lenl[i]] = true;
    }
  }
  if (!dp[k]) ans1++;
  printf("%d %d\n", ans1, ans2);
  return 0;
}

```