#include <bits/stdc++.h>
using namespace std;
int min_missing(vector<int> cycles, int k) {
  const auto n = max(*max_element(begin(cycles), end(cycles)), k);
  auto counts = vector<int>(n + 1);
  for (const auto length : cycles) counts[length]++;
  auto possible = bitset<int(1e6 + 1)>();
  possible.set(0);
  for (auto i = 2; i <= n; i++) {
    auto remaining = counts[i];
    for (auto size = 1; size <= remaining; size *= 2) {
      possible |= possible << size * i;
      remaining -= size;
    }
    if (remaining) possible |= possible << remaining * i;
  }
  return possible[k] ? k : k + 1;
}
int max_missing(vector<int> cycles, int k) {
  auto result = 0;
  auto odds = 0;
  for (const auto length : cycles) {
    const auto uses = min(k, length / 2);
    k -= uses;
    result += 2 * uses;
    if (length % 2 == 1) odds++;
  }
  return result + min(k, odds);
}
int main() {
  ios::sync_with_stdio(false);
  int n, k;
  cin >> n >> k;
  auto permutation = vector<int>(n);
  for (auto& p : permutation) {
    cin >> p;
    p--;
  }
  auto cycles = vector<int>();
  auto seen = vector<bool>(n);
  for (auto i = 0; i < n; i++)
    if (!seen[i]) {
      auto length = 0;
      for (auto j = i; !seen[j]; j = permutation[j]) {
        seen[j] = true;
        length++;
      }
      cycles.push_back(length);
    }
  cout << min_missing(cycles, k) << " " << max_missing(cycles, k) << endl;
}
