#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
int solve();
int main() {
  srand(0);
  return solve();
}
const int MAXN = 1e6 + 7;
const int C = 100;
int to[MAXN], cnt[MAXN];
bool used[MAXN];
string dp(MAXN, '0');
int solve() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int v = 1; v <= (int)n; v++) scanf("%d", to + v);
  for (int v = 1; v <= (int)n; v++) {
    if (!used[v]) {
      int curv = v, len = 0;
      while (!used[curv]) {
        used[curv] = true;
        curv = to[curv];
        len++;
      }
      cnt[len]++;
    }
  }
  dp[0] = '1';
  for (int w = 1; w <= C; w++) {
    for (int i = 0; i < w; i++) {
      int q = MAXN;
      for (int pw = i; pw < MAXN; pw += w) {
        if (dp[pw] == '1') {
          q = 0;
        } else {
          if (q <= cnt[w]) {
            dp[pw] = '1';
          }
        }
        q++;
      }
    }
  }
  reverse(dp.begin(), dp.end());
  bitset<MAXN> bit_dp(dp);
  for (int w = C + 1; w < MAXN; w++) {
    for (int i = 0; i < (int)cnt[w]; i++) {
      bit_dp |= bit_dp << w;
    }
  }
  int minim_ans = 0, maxim_ans = 0, q = k, left = 0;
  minim_ans = k + 1 - bit_dp[k];
  for (int w = MAXN - 1; w >= 0; w--) {
    for (int i = 0; i < (int)cnt[w]; i++) {
      int d = min(q, w / 2);
      maxim_ans += d * 2;
      q -= d;
      left += w - d * 2;
    }
  }
  maxim_ans += min(q, left);
  cout << minim_ans << ' ' << maxim_ans;
  return 0;
}

### Prompt

Develop a solution in CPP 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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
int solve();
int main() {
  srand(0);
  return solve();
}
const int MAXN = 1e6 + 7;
const int C = 100;
int to[MAXN], cnt[MAXN];
bool used[MAXN];
string dp(MAXN, '0');
int solve() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int v = 1; v <= (int)n; v++) scanf("%d", to + v);
  for (int v = 1; v <= (int)n; v++) {
    if (!used[v]) {
      int curv = v, len = 0;
      while (!used[curv]) {
        used[curv] = true;
        curv = to[curv];
        len++;
      }
      cnt[len]++;
    }
  }
  dp[0] = '1';
  for (int w = 1; w <= C; w++) {
    for (int i = 0; i < w; i++) {
      int q = MAXN;
      for (int pw = i; pw < MAXN; pw += w) {
        if (dp[pw] == '1') {
          q = 0;
        } else {
          if (q <= cnt[w]) {
            dp[pw] = '1';
          }
        }
        q++;
      }
    }
  }
  reverse(dp.begin(), dp.end());
  bitset<MAXN> bit_dp(dp);
  for (int w = C + 1; w < MAXN; w++) {
    for (int i = 0; i < (int)cnt[w]; i++) {
      bit_dp |= bit_dp << w;
    }
  }
  int minim_ans = 0, maxim_ans = 0, q = k, left = 0;
  minim_ans = k + 1 - bit_dp[k];
  for (int w = MAXN - 1; w >= 0; w--) {
    for (int i = 0; i < (int)cnt[w]; i++) {
      int d = min(q, w / 2);
      maxim_ans += d * 2;
      q -= d;
      left += w - d * 2;
    }
  }
  maxim_ans += min(q, left);
  cout << minim_ans << ' ' << maxim_ans;
  return 0;
}

```