#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
const int maxn = 1e6 + 2, SQ = 90;
int p[maxn], cnt[SQ], ps[maxn];
vector<int> C, D, E, S;
bitset<maxn> mark, knap;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> p[i];
    p[i]--;
  }
  for (int i = 0; i < n; i++) {
    if (mark[i]) continue;
    mark[i] = 1;
    int t = 1, cur = p[i];
    while (cur != i) {
      mark[cur] = 1;
      t++;
      cur = p[cur];
    }
    C.push_back(t);
    if (t % 2)
      E.push_back(t);
    else
      D.push_back(t);
    if (t >= SQ)
      S.push_back(t);
    else
      cnt[t]++;
  }
  sort(C.begin(), C.end());
  sort(D.begin(), D.end());
  sort(E.begin(), E.end());
  knap[0] = 1;
  for (int i = 0; i < S.size(); i++) {
    knap |= knap << S[i];
  }
  ps[0] = 1;
  for (int i = 1; i <= k; i++) ps[i] = knap[i] + ps[i - 1];
  for (int i = 1; i < SQ; i++) {
    for (int j = i; j <= k; j++) {
      if (j >= (cnt[i] + 1) * i)
        knap[j] = knap[j] | (bool)(ps[j] - ps[j - (cnt[i] + 1) * i]);
      else {
        knap[j] = knap[j] | (bool)(ps[j]);
      }
    }
    ps[i] = knap[i];
    for (int j = i + 1; j <= k; j++) {
      ps[j] = ps[j - i - 1] + knap[j];
    }
    if (knap[k]) {
      break;
    }
  }
  if (knap[k])
    cout << k << ' ';
  else
    cout << k + 1 << ' ';
  int mn = 0;
  for (int i = (int)D.size() - 1; i + 1; i--) {
    if (D[i] / 2 > k) {
      mn += k * 2;
      k = 0;
    } else {
      k -= D[i] / 2;
      mn += D[i];
    }
    if (!k) break;
  }
  for (int i = (int)E.size() - 1; i + 1; i--) {
    if (E[i] / 2 > k) {
      mn += 2 * k;
      k = 0;
    } else {
      k -= E[i] / 2;
      mn += E[i] - 1;
    }
    if (!k) break;
  }
  for (int i = 0; i < E.size() && k; i++) {
    k--;
    mn++;
  }
  cout << mn;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
#pragma GCC optimize("O3,Ofast,no-stack-protector,unroll-loops,fast-math")
const int maxn = 1e6 + 2, SQ = 90;
int p[maxn], cnt[SQ], ps[maxn];
vector<int> C, D, E, S;
bitset<maxn> mark, knap;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> p[i];
    p[i]--;
  }
  for (int i = 0; i < n; i++) {
    if (mark[i]) continue;
    mark[i] = 1;
    int t = 1, cur = p[i];
    while (cur != i) {
      mark[cur] = 1;
      t++;
      cur = p[cur];
    }
    C.push_back(t);
    if (t % 2)
      E.push_back(t);
    else
      D.push_back(t);
    if (t >= SQ)
      S.push_back(t);
    else
      cnt[t]++;
  }
  sort(C.begin(), C.end());
  sort(D.begin(), D.end());
  sort(E.begin(), E.end());
  knap[0] = 1;
  for (int i = 0; i < S.size(); i++) {
    knap |= knap << S[i];
  }
  ps[0] = 1;
  for (int i = 1; i <= k; i++) ps[i] = knap[i] + ps[i - 1];
  for (int i = 1; i < SQ; i++) {
    for (int j = i; j <= k; j++) {
      if (j >= (cnt[i] + 1) * i)
        knap[j] = knap[j] | (bool)(ps[j] - ps[j - (cnt[i] + 1) * i]);
      else {
        knap[j] = knap[j] | (bool)(ps[j]);
      }
    }
    ps[i] = knap[i];
    for (int j = i + 1; j <= k; j++) {
      ps[j] = ps[j - i - 1] + knap[j];
    }
    if (knap[k]) {
      break;
    }
  }
  if (knap[k])
    cout << k << ' ';
  else
    cout << k + 1 << ' ';
  int mn = 0;
  for (int i = (int)D.size() - 1; i + 1; i--) {
    if (D[i] / 2 > k) {
      mn += k * 2;
      k = 0;
    } else {
      k -= D[i] / 2;
      mn += D[i];
    }
    if (!k) break;
  }
  for (int i = (int)E.size() - 1; i + 1; i--) {
    if (E[i] / 2 > k) {
      mn += 2 * k;
      k = 0;
    } else {
      k -= E[i] / 2;
      mn += E[i] - 1;
    }
    if (!k) break;
  }
  for (int i = 0; i < E.size() && k; i++) {
    k--;
    mn++;
  }
  cout << mn;
}

```