#include <bits/stdc++.h>
using namespace std;
const int N = 1 << 20;
struct SSS {
  int tot;
  bitset<N> ok;
  SSS(const vector<int>& a) : tot(0), ok(1) {
    vector<int> c(N, 0);
    for (int x : a) tot += x, c[x]++;
    for (int sum = 0, i = 1; i <= tot >> 1; i++)
      if (c[i] > 0) {
        for (int m = min(tot >> 1, sum += i * c[i]), j = max(m - i + 1, 1);
             j <= m; j++) {
          int cnt = 0;
          for (int k = 0; k < c[i] && j >= i * k; k++) cnt += ok[j - i * k];
          for (int k = j; k > 0; k -= i) {
            cnt -= ok[k];
            if (k >= i * c[i]) cnt += ok[k - i * c[i]];
            if (cnt > 0) ok[k] = true;
          }
        }
      }
  }
  bool operator[](int n) const {
    return n < 0 || n > tot ? false : ok[min(n, tot - n)];
  }
};
int mini(const vector<int>& a, int m) { return SSS(a)[m] ? m : m + 1; }
int maxi(const vector<int>& a, int m) {
  int ans = 0, odd = 0;
  for (int x : a) {
    int tmp = min(x >> 1, m);
    odd += x & 1;
    ans += tmp << 1;
    m -= tmp;
  }
  return ans + min(odd, m);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> p(n + 1, 0);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  vector<int> a;
  for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (int x = i; p[x] > 0; cnt++) {
      int tmp = p[x];
      p[x] = 0;
      x = tmp;
    }
    if (cnt > 0) a.push_back(cnt);
  }
  printf("%d %d\n", mini(a, m), maxi(a, m));
}

### Prompt

Please create a solution in Cpp 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 int N = 1 << 20;
struct SSS {
  int tot;
  bitset<N> ok;
  SSS(const vector<int>& a) : tot(0), ok(1) {
    vector<int> c(N, 0);
    for (int x : a) tot += x, c[x]++;
    for (int sum = 0, i = 1; i <= tot >> 1; i++)
      if (c[i] > 0) {
        for (int m = min(tot >> 1, sum += i * c[i]), j = max(m - i + 1, 1);
             j <= m; j++) {
          int cnt = 0;
          for (int k = 0; k < c[i] && j >= i * k; k++) cnt += ok[j - i * k];
          for (int k = j; k > 0; k -= i) {
            cnt -= ok[k];
            if (k >= i * c[i]) cnt += ok[k - i * c[i]];
            if (cnt > 0) ok[k] = true;
          }
        }
      }
  }
  bool operator[](int n) const {
    return n < 0 || n > tot ? false : ok[min(n, tot - n)];
  }
};
int mini(const vector<int>& a, int m) { return SSS(a)[m] ? m : m + 1; }
int maxi(const vector<int>& a, int m) {
  int ans = 0, odd = 0;
  for (int x : a) {
    int tmp = min(x >> 1, m);
    odd += x & 1;
    ans += tmp << 1;
    m -= tmp;
  }
  return ans + min(odd, m);
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  vector<int> p(n + 1, 0);
  for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
  vector<int> a;
  for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (int x = i; p[x] > 0; cnt++) {
      int tmp = p[x];
      p[x] = 0;
      x = tmp;
    }
    if (cnt > 0) a.push_back(cnt);
  }
  printf("%d %d\n", mini(a, m), maxi(a, m));
}

```