#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int p[N], vis[N], n, k, cnt[N], pr[N], old_cnt;
vector<int> len;
unsigned int f[N], g[N];
int main() {
  scanf("%d %d", &n, &k);
  if (!k) {
    puts("0 0");
    return 0;
  }
  int i, j;
  for (i = 1; i <= n; i++) {
    scanf("%d", &p[i]);
  }
  int s;
  for (i = 1; i <= n; i++) {
    if (!vis[i]) {
      s = i;
      int curLen = 0;
      while (!vis[s]) {
        vis[s] = 1;
        curLen++;
        s = p[s];
      }
      cnt[curLen]++;
    }
  }
  for (i = 1; i < N; i++) {
    old_cnt = cnt[i];
    for (j = 0; j <= 20; j++) {
      if (cnt[i] >= (1 << j)) {
        cnt[i] -= (1 << j);
        len.push_back((1 << j) * i);
      }
    }
    if (cnt[i]) {
      len.push_back(cnt[i] * i);
    }
    cnt[i] = old_cnt;
  }
  f[1] = 1;
  int mxNum, num, nxtNum, rest, shift;
  pr[0] = 0;
  for (i = 1; i <= (int(len.size())); i++) {
    for (j = 1; j <= (N >> 5); j++) {
      g[j] = f[j];
    }
    pr[i] = pr[i - 1] + len[i - 1];
    mxNum = pr[i] / 32 + 1;
    rest = len[i - 1] % 32, shift = len[i - 1] / 32;
    for (j = mxNum; j >= 1; j--) {
      nxtNum = j + shift;
      if (!rest) {
        g[nxtNum] |= f[j];
      } else {
        unsigned int rb = (f[j] >> (32 - rest));
        unsigned int lb = f[j] - (rb << (32 - rest));
        lb = (lb << rest);
        g[nxtNum + 1] |= rb;
        g[nxtNum] |= lb;
      }
    }
    for (j = 1; j <= (N >> 5); j++) {
      f[j] = g[j];
    }
  }
  int mn = k, mx = 0;
  num = k / 32 + 1, rest = k % 32;
  if (((f[num] >> rest) & 1) != 1) {
    mn++;
  }
  for (i = 1; i < N; i++) {
    for (j = 1; j <= cnt[i]; j++) {
      if (!k) {
        break;
      }
      if (k > i / 2) {
        k -= i / 2;
        mx += (i / 2) * 2;
      } else {
        mx += k * 2;
        k = 0;
      }
    }
  }
  mx += k;
  mx = min(mx, n);
  printf("%d %d", mn, mx);
  return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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 int N = 1e6 + 5;
int p[N], vis[N], n, k, cnt[N], pr[N], old_cnt;
vector<int> len;
unsigned int f[N], g[N];
int main() {
  scanf("%d %d", &n, &k);
  if (!k) {
    puts("0 0");
    return 0;
  }
  int i, j;
  for (i = 1; i <= n; i++) {
    scanf("%d", &p[i]);
  }
  int s;
  for (i = 1; i <= n; i++) {
    if (!vis[i]) {
      s = i;
      int curLen = 0;
      while (!vis[s]) {
        vis[s] = 1;
        curLen++;
        s = p[s];
      }
      cnt[curLen]++;
    }
  }
  for (i = 1; i < N; i++) {
    old_cnt = cnt[i];
    for (j = 0; j <= 20; j++) {
      if (cnt[i] >= (1 << j)) {
        cnt[i] -= (1 << j);
        len.push_back((1 << j) * i);
      }
    }
    if (cnt[i]) {
      len.push_back(cnt[i] * i);
    }
    cnt[i] = old_cnt;
  }
  f[1] = 1;
  int mxNum, num, nxtNum, rest, shift;
  pr[0] = 0;
  for (i = 1; i <= (int(len.size())); i++) {
    for (j = 1; j <= (N >> 5); j++) {
      g[j] = f[j];
    }
    pr[i] = pr[i - 1] + len[i - 1];
    mxNum = pr[i] / 32 + 1;
    rest = len[i - 1] % 32, shift = len[i - 1] / 32;
    for (j = mxNum; j >= 1; j--) {
      nxtNum = j + shift;
      if (!rest) {
        g[nxtNum] |= f[j];
      } else {
        unsigned int rb = (f[j] >> (32 - rest));
        unsigned int lb = f[j] - (rb << (32 - rest));
        lb = (lb << rest);
        g[nxtNum + 1] |= rb;
        g[nxtNum] |= lb;
      }
    }
    for (j = 1; j <= (N >> 5); j++) {
      f[j] = g[j];
    }
  }
  int mn = k, mx = 0;
  num = k / 32 + 1, rest = k % 32;
  if (((f[num] >> rest) & 1) != 1) {
    mn++;
  }
  for (i = 1; i < N; i++) {
    for (j = 1; j <= cnt[i]; j++) {
      if (!k) {
        break;
      }
      if (k > i / 2) {
        k -= i / 2;
        mx += (i / 2) * 2;
      } else {
        mx += k * 2;
        k = 0;
      }
    }
  }
  mx += k;
  mx = min(mx, n);
  printf("%d %d", mn, mx);
  return 0;
}

```