#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;
}
