#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const long long _INF = 0xc0c0c0c0c0c0c0c0;
const long long mod = (int)1e9 + 7;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long ksm(long long a, long long b, long long mod) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}
long long inv2(long long a, long long mod) { return ksm(a, mod - 2, mod); }
void exgcd(long long a, long long b, long long &x, long long &y, long long &d) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    exgcd(b, a % b, y, x, d);
    y -= x * (a / b);
  }
}
const int MAX_N = 1000025;
int cnt, belong[MAX_N], Size[MAX_N], arr[MAX_N], v[MAX_N], w[MAX_N];
bool dp[MAX_N];
void dfs(int x) {
  belong[x] = cnt;
  if (belong[arr[x]] != -1) return;
  dfs(arr[x]);
  Size[cnt]++;
}
vector<int> vt, vt_;
map<int, int> mp;
set<int> st;
bool cmp(int a, int b) { return a > b; }
int main() {
  int n, m, k, bc = 0;
  cnt = 0;
  scanf("%d%d", &n, &m);
  k = m;
  for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
  memset(belong, -1, sizeof(belong));
  memset(dp, false, sizeof(dp));
  dp[0] = true;
  for (int i = 1; i <= n; ++i) {
    if (belong[i] == -1) {
      cnt++;
      dfs(i);
      Size[cnt]++;
    }
  }
  for (int i = 1; i <= cnt; ++i) {
    st.insert(Size[i]);
    mp[Size[i]]++;
    if (Size[i] % 2 == 0)
      vt.push_back(Size[i]);
    else
      vt_.push_back(Size[i]);
  }
  sort(vt.begin(), vt.end(), cmp);
  sort(vt_.begin(), vt_.end(), cmp);
  int ans = 0, ans_ = 0, sz = vt.size(), sz_ = vt_.size();
  for (int i = 0; i < sz; ++i) {
    if (m >= vt[i] / 2) {
      m -= vt[i] / 2;
      ans_ += vt[i];
    } else if (m == 0)
      break;
    else {
      ans_ += m * 2;
      m = 0;
      break;
    }
  }
  for (int i = 0; i < sz_; ++i) {
    if (m >= vt_[i] / 2) {
      m -= vt_[i] / 2;
      ans_ += vt_[i] - 1;
      bc++;
    } else if (m == 0)
      break;
    else {
      ans_ += m * 2;
      m = 0;
      break;
    }
  }
  ans_ += min(m, bc);
  m = k;
  int now = 0;
  set<int>::iterator it;
  for (it = st.begin(); it != st.end(); ++it) {
    v[++now] = *it;
    w[now] = mp[*it];
  }
  for (int i = 1; i <= now; ++i) {
    if (v[i] * w[i] >= m) {
      for (int j = v[i]; j <= m; ++j) dp[j] = dp[j - v[i]] | dp[j];
    } else {
      for (int k = 0; k <= 30; k++) {
        long long tmp = (1ll << k);
        if (w[i] >= tmp) {
          w[i] -= tmp;
          for (int j = m; j >= tmp * v[i]; --j)
            dp[j] = dp[j - tmp * v[i]] | dp[j];
          if (w[i] == 0) break;
        } else {
          for (int j = m; j >= w[i] * v[i]; --j)
            dp[j] = dp[j - w[i] * v[i]] | dp[j];
          w[i] = 0;
          break;
        }
      }
    }
  }
  if (dp[k])
    ans = k;
  else
    ans = k + 1;
  printf("%d %d\n", ans, ans_);
  return 0;
}

### Prompt

Generate a cpp solution 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 inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const long long _INF = 0xc0c0c0c0c0c0c0c0;
const long long mod = (int)1e9 + 7;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long ksm(long long a, long long b, long long mod) {
  int ans = 1;
  while (b) {
    if (b & 1) ans = (ans * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}
long long inv2(long long a, long long mod) { return ksm(a, mod - 2, mod); }
void exgcd(long long a, long long b, long long &x, long long &y, long long &d) {
  if (!b) {
    d = a;
    x = 1;
    y = 0;
  } else {
    exgcd(b, a % b, y, x, d);
    y -= x * (a / b);
  }
}
const int MAX_N = 1000025;
int cnt, belong[MAX_N], Size[MAX_N], arr[MAX_N], v[MAX_N], w[MAX_N];
bool dp[MAX_N];
void dfs(int x) {
  belong[x] = cnt;
  if (belong[arr[x]] != -1) return;
  dfs(arr[x]);
  Size[cnt]++;
}
vector<int> vt, vt_;
map<int, int> mp;
set<int> st;
bool cmp(int a, int b) { return a > b; }
int main() {
  int n, m, k, bc = 0;
  cnt = 0;
  scanf("%d%d", &n, &m);
  k = m;
  for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]);
  memset(belong, -1, sizeof(belong));
  memset(dp, false, sizeof(dp));
  dp[0] = true;
  for (int i = 1; i <= n; ++i) {
    if (belong[i] == -1) {
      cnt++;
      dfs(i);
      Size[cnt]++;
    }
  }
  for (int i = 1; i <= cnt; ++i) {
    st.insert(Size[i]);
    mp[Size[i]]++;
    if (Size[i] % 2 == 0)
      vt.push_back(Size[i]);
    else
      vt_.push_back(Size[i]);
  }
  sort(vt.begin(), vt.end(), cmp);
  sort(vt_.begin(), vt_.end(), cmp);
  int ans = 0, ans_ = 0, sz = vt.size(), sz_ = vt_.size();
  for (int i = 0; i < sz; ++i) {
    if (m >= vt[i] / 2) {
      m -= vt[i] / 2;
      ans_ += vt[i];
    } else if (m == 0)
      break;
    else {
      ans_ += m * 2;
      m = 0;
      break;
    }
  }
  for (int i = 0; i < sz_; ++i) {
    if (m >= vt_[i] / 2) {
      m -= vt_[i] / 2;
      ans_ += vt_[i] - 1;
      bc++;
    } else if (m == 0)
      break;
    else {
      ans_ += m * 2;
      m = 0;
      break;
    }
  }
  ans_ += min(m, bc);
  m = k;
  int now = 0;
  set<int>::iterator it;
  for (it = st.begin(); it != st.end(); ++it) {
    v[++now] = *it;
    w[now] = mp[*it];
  }
  for (int i = 1; i <= now; ++i) {
    if (v[i] * w[i] >= m) {
      for (int j = v[i]; j <= m; ++j) dp[j] = dp[j - v[i]] | dp[j];
    } else {
      for (int k = 0; k <= 30; k++) {
        long long tmp = (1ll << k);
        if (w[i] >= tmp) {
          w[i] -= tmp;
          for (int j = m; j >= tmp * v[i]; --j)
            dp[j] = dp[j - tmp * v[i]] | dp[j];
          if (w[i] == 0) break;
        } else {
          for (int j = m; j >= w[i] * v[i]; --j)
            dp[j] = dp[j - w[i] * v[i]] | dp[j];
          w[i] = 0;
          break;
        }
      }
    }
  }
  if (dp[k])
    ans = k;
  else
    ans = k + 1;
  printf("%d %d\n", ans, ans_);
  return 0;
}

```