#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7, M = 20;
int pi[N], sz[N];
bool mark[N];
bitset<N / 2> dp;
int arr[40 * N], cnt_[N];
bool see[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int cnt = 0, n, k;
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", pi + i);
  for (int i = 1; i <= n; i++) {
    if (mark[i]) continue;
    int x = i;
    while (!mark[x]) {
      sz[cnt]++;
      mark[x] = true;
      x = pi[x];
    }
    cnt++;
  }
  int mx = 0, odd = 0;
  for (int i = 0; i < cnt; i++) {
    mx += sz[i] / 2;
    if (sz[i] % 2) odd++;
  }
  if (mx >= k)
    mx = 2 * k;
  else
    mx = min(n, 2 * mx + min(odd, k - mx));
  dp[0] = 1;
  int mn = k;
  if (k > n / 2) k = n - k;
  if (cnt <= 1e3) {
    for (int i = 0; i < cnt; i++) {
      dp |= dp << (sz[i]);
      if (dp[k]) {
        printf("%d %d\n", mn, mx);
        return 0;
      }
    }
    if (!dp[k]) mn++;
    printf("%d %d\n", mn, mx);
    return 0;
  }
  for (int i = 0; i < cnt; i++) cnt_[sz[i]]++;
  int s = 0;
  for (int i = 0; i < cnt; i++) {
    if (see[sz[i]]) continue;
    see[sz[i]] = true;
    bool f = false;
    for (int j = M - 1; j >= 0; j--) {
      if (cnt_[sz[i]] & (1 << j)) {
        if (f)
          arr[s++] = sz[i] * (1LL << j);
        else {
          for (int k = j - 1; k >= 0; k--) {
            arr[s++] = sz[i] * (1LL << k);
          }
          arr[s++] = sz[i];
          f = true;
        }
      }
    }
  }
  for (int i = 0; i < s; i++) {
    dp |= dp << (arr[i]);
    if (dp[k]) {
      printf("%d %d\n", mn, mx);
      return 0;
    }
  }
  printf("%d %d\n", mn + 1, mx);
}

### Prompt

In CPP, your task is to solve 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 int N = 1e6 + 10, mod = 1e9 + 7, M = 20;
int pi[N], sz[N];
bool mark[N];
bitset<N / 2> dp;
int arr[40 * N], cnt_[N];
bool see[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int cnt = 0, n, k;
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", pi + i);
  for (int i = 1; i <= n; i++) {
    if (mark[i]) continue;
    int x = i;
    while (!mark[x]) {
      sz[cnt]++;
      mark[x] = true;
      x = pi[x];
    }
    cnt++;
  }
  int mx = 0, odd = 0;
  for (int i = 0; i < cnt; i++) {
    mx += sz[i] / 2;
    if (sz[i] % 2) odd++;
  }
  if (mx >= k)
    mx = 2 * k;
  else
    mx = min(n, 2 * mx + min(odd, k - mx));
  dp[0] = 1;
  int mn = k;
  if (k > n / 2) k = n - k;
  if (cnt <= 1e3) {
    for (int i = 0; i < cnt; i++) {
      dp |= dp << (sz[i]);
      if (dp[k]) {
        printf("%d %d\n", mn, mx);
        return 0;
      }
    }
    if (!dp[k]) mn++;
    printf("%d %d\n", mn, mx);
    return 0;
  }
  for (int i = 0; i < cnt; i++) cnt_[sz[i]]++;
  int s = 0;
  for (int i = 0; i < cnt; i++) {
    if (see[sz[i]]) continue;
    see[sz[i]] = true;
    bool f = false;
    for (int j = M - 1; j >= 0; j--) {
      if (cnt_[sz[i]] & (1 << j)) {
        if (f)
          arr[s++] = sz[i] * (1LL << j);
        else {
          for (int k = j - 1; k >= 0; k--) {
            arr[s++] = sz[i] * (1LL << k);
          }
          arr[s++] = sz[i];
          f = true;
        }
      }
    }
  }
  for (int i = 0; i < s; i++) {
    dp |= dp << (arr[i]);
    if (dp[k]) {
      printf("%d %d\n", mn, mx);
      return 0;
    }
  }
  printf("%d %d\n", mn + 1, mx);
}

```