#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);
template <class T, class S>
inline void add(T& a, S b) {
  a += b;
  if (a >= mod) a -= mod;
}
template <class T, class S>
inline void sub(T& a, S b) {
  a -= b;
  if (a < 0) a += mod;
}
template <class T, class S>
inline bool chkmax(T& a, S b) {
  return a < b ? a = b, true : false;
}
template <class T, class S>
inline bool chkmin(T& a, S b) {
  return a > b ? a = b, true : false;
}
int n, k, p[N], c[N], num[N], cnt;
bool vis[N];
bitset<1000001> dp;
vector<int> oo;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    int u = i;
    cnt++;
    while (!vis[u]) {
      vis[u] = true;
      c[cnt]++;
      u = p[u];
    }
  }
  int one = 0, two = 0;
  for (int i = 1; i <= cnt; i++)
    (c[i] & 1) ? one++, two += c[i] / 2 : two += c[i] / 2;
  int mnans = 0, mxans = 0;
  if (two >= k)
    mxans = 2 * k;
  else {
    mxans += two * 2 + (k - two);
    chkmin(mxans, n);
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) oo.push_back(c[i]);
  sort((oo).begin(), (oo).end());
  oo.erase(unique((oo).begin(), (oo).end()), oo.end());
  for (int i = 1; i <= n; i++)
    num[lower_bound((oo).begin(), (oo).end(), c[i]) - oo.begin()]++;
  for (int i = 0; i < ((int)oo.size()); i++) {
    for (int j = 0; (1 << j) <= num[i]; j++) {
      int val = (1 << j) * oo[i];
      num[i] -= 1 << j;
      dp |= dp << val;
    }
    if (num[i]) {
      int val = num[i] * oo[i];
      dp |= dp << val;
    }
  }
  mnans = dp[k] ? k : k + 1;
  printf("%d %d\n", mnans, mxans);
  return 0;
}

### Prompt

Create a solution in CPP for 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 + 7;
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1);
template <class T, class S>
inline void add(T& a, S b) {
  a += b;
  if (a >= mod) a -= mod;
}
template <class T, class S>
inline void sub(T& a, S b) {
  a -= b;
  if (a < 0) a += mod;
}
template <class T, class S>
inline bool chkmax(T& a, S b) {
  return a < b ? a = b, true : false;
}
template <class T, class S>
inline bool chkmin(T& a, S b) {
  return a > b ? a = b, true : false;
}
int n, k, p[N], c[N], num[N], cnt;
bool vis[N];
bitset<1000001> dp;
vector<int> oo;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  for (int i = 1; i <= n; i++) {
    if (vis[i]) continue;
    int u = i;
    cnt++;
    while (!vis[u]) {
      vis[u] = true;
      c[cnt]++;
      u = p[u];
    }
  }
  int one = 0, two = 0;
  for (int i = 1; i <= cnt; i++)
    (c[i] & 1) ? one++, two += c[i] / 2 : two += c[i] / 2;
  int mnans = 0, mxans = 0;
  if (two >= k)
    mxans = 2 * k;
  else {
    mxans += two * 2 + (k - two);
    chkmin(mxans, n);
  }
  dp[0] = 1;
  for (int i = 1; i <= n; i++) oo.push_back(c[i]);
  sort((oo).begin(), (oo).end());
  oo.erase(unique((oo).begin(), (oo).end()), oo.end());
  for (int i = 1; i <= n; i++)
    num[lower_bound((oo).begin(), (oo).end(), c[i]) - oo.begin()]++;
  for (int i = 0; i < ((int)oo.size()); i++) {
    for (int j = 0; (1 << j) <= num[i]; j++) {
      int val = (1 << j) * oo[i];
      num[i] -= 1 << j;
      dp |= dp << val;
    }
    if (num[i]) {
      int val = num[i] * oo[i];
      dp |= dp << val;
    }
  }
  mnans = dp[k] ? k : k + 1;
  printf("%d %d\n", mnans, mxans);
  return 0;
}

```