#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int maxN = 1100000;
int n, k;
int p[maxN], ip[maxN];
bool used[maxN];
pair<int, int> trivial(int n, int k) {
  int mn = n, mx = 0;
  for (int i = 0; i < (1 << n); ++i) {
    int cnt = 0;
    for (int j = 0; j < n; ++j) {
      if (i & (1 << j)) {
        ++cnt;
      }
    }
    if (cnt != k) {
      continue;
    }
    int r = 0;
    for (int j = 0; j < n; ++j) {
      if ((i & (1 << j)) || (i & (1 << ip[j]))) {
        ++r;
      }
    }
    mn = min(mn, r);
    mx = max(mx, r);
  }
  return make_pair(mn, mx);
}
int calcMax(vector<int> &cycles, int n, int k) {
  multiset<int> S;
  for (int i = 0; i < cycles.size(); ++i) {
    int m = cycles[i];
    for (int j = 0; j < m / 2; ++j) {
      S.insert(-2);
    }
    for (int j = 0; j < m / 2; ++j) {
      S.insert(0);
    }
    if (m % 2 == 1) {
      S.insert(-1);
    }
  }
  int a = 0;
  for (int i = 0; i < k; ++i) {
    int v = *S.begin();
    a -= v;
    S.erase(S.begin());
  }
  return a;
}
int cnt[maxN];
int id[maxN];
bool check(vector<pair<int, int> > &p, int s) {
  cnt[0] = 0;
  for (int i = 0; i < p.size(); ++i) {
    int m = p[i].first;
    int v = p[i].second;
    for (int j = 0; j + m <= s; ++j) {
      if (cnt[j] == -1 || cnt[j + m] != -1) {
        continue;
      }
      if (id[j] < i || cnt[j] + 1 <= v) {
        cnt[j + m] = (id[j] < i ? 1 : cnt[j] + 1);
        id[j + m] = i;
      }
    }
    if (cnt[s] != -1) {
      return true;
    }
  }
  return false;
}
int calcMin(vector<int> &cycles, int n, int k) {
  vector<pair<int, int> > p;
  int l = 0;
  for (int i = 1; i <= cycles.size(); ++i) {
    if (i == cycles.size() || cycles[i] > cycles[i - 1]) {
      p.push_back(make_pair(cycles[l], i - l));
      l = i;
    }
  }
  if (check(p, min(k, n - k))) {
    return k;
  }
  return k + 1;
}
pair<int, int> clever(int n, int k) {
  vector<int> cycles;
  for (int i = 0; i < n; ++i) {
    used[i] = false;
  }
  for (int i = 0; i <= n; ++i) {
    cnt[i] = -1;
    id[i] = -1;
  }
  for (int i = 0; i < n; ++i) {
    if (used[i]) {
      continue;
    }
    int v = i;
    int len = 0;
    while (!used[v]) {
      ++len;
      used[v] = true;
      v = p[v];
    }
    cycles.push_back(len);
  }
  sort(cycles.begin(), cycles.end());
  int a = calcMax(cycles, n, k);
  int b = calcMin(cycles, n, k);
  return make_pair(b, a);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &p[i]);
    --p[i];
    ip[p[i]] = i;
  }
  pair<int, int> res = clever(n, k);
  printf("%d %d\n", res.first, res.second);
  return 0;
  for (int n = 1; n <= 10; ++n) {
    cerr << n << endl;
    for (int k = 0; k <= n; ++k) {
      vector<int> a(n);
      for (int i = 0; i < n; ++i) {
        a[i] = i;
      }
      do {
        bool bad = false;
        for (int i = 0; i < n; ++i) {
          p[i] = a[i];
          ip[p[i]] = i;
          if (a[i] == i) {
            bad = true;
          }
        }
        if (bad) {
          continue;
        }
        if (trivial(n, k) != clever(n, k)) {
          for (int j = 0; j < n; ++j) {
            printf("%d ", a[j] + 1);
          }
          printf("\n");
          printf("%d\n", k);
          printf("%d %d\n", trivial(n, k).first, trivial(n, k).second);
          printf("%d %d\n", clever(n, k).first, clever(n, k).second);
          return 0;
        }
      } while (next_permutation(a.begin(), a.end()));
    }
  }
  return 0;
}

### Prompt

In cpp, your task is to solve 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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int maxN = 1100000;
int n, k;
int p[maxN], ip[maxN];
bool used[maxN];
pair<int, int> trivial(int n, int k) {
  int mn = n, mx = 0;
  for (int i = 0; i < (1 << n); ++i) {
    int cnt = 0;
    for (int j = 0; j < n; ++j) {
      if (i & (1 << j)) {
        ++cnt;
      }
    }
    if (cnt != k) {
      continue;
    }
    int r = 0;
    for (int j = 0; j < n; ++j) {
      if ((i & (1 << j)) || (i & (1 << ip[j]))) {
        ++r;
      }
    }
    mn = min(mn, r);
    mx = max(mx, r);
  }
  return make_pair(mn, mx);
}
int calcMax(vector<int> &cycles, int n, int k) {
  multiset<int> S;
  for (int i = 0; i < cycles.size(); ++i) {
    int m = cycles[i];
    for (int j = 0; j < m / 2; ++j) {
      S.insert(-2);
    }
    for (int j = 0; j < m / 2; ++j) {
      S.insert(0);
    }
    if (m % 2 == 1) {
      S.insert(-1);
    }
  }
  int a = 0;
  for (int i = 0; i < k; ++i) {
    int v = *S.begin();
    a -= v;
    S.erase(S.begin());
  }
  return a;
}
int cnt[maxN];
int id[maxN];
bool check(vector<pair<int, int> > &p, int s) {
  cnt[0] = 0;
  for (int i = 0; i < p.size(); ++i) {
    int m = p[i].first;
    int v = p[i].second;
    for (int j = 0; j + m <= s; ++j) {
      if (cnt[j] == -1 || cnt[j + m] != -1) {
        continue;
      }
      if (id[j] < i || cnt[j] + 1 <= v) {
        cnt[j + m] = (id[j] < i ? 1 : cnt[j] + 1);
        id[j + m] = i;
      }
    }
    if (cnt[s] != -1) {
      return true;
    }
  }
  return false;
}
int calcMin(vector<int> &cycles, int n, int k) {
  vector<pair<int, int> > p;
  int l = 0;
  for (int i = 1; i <= cycles.size(); ++i) {
    if (i == cycles.size() || cycles[i] > cycles[i - 1]) {
      p.push_back(make_pair(cycles[l], i - l));
      l = i;
    }
  }
  if (check(p, min(k, n - k))) {
    return k;
  }
  return k + 1;
}
pair<int, int> clever(int n, int k) {
  vector<int> cycles;
  for (int i = 0; i < n; ++i) {
    used[i] = false;
  }
  for (int i = 0; i <= n; ++i) {
    cnt[i] = -1;
    id[i] = -1;
  }
  for (int i = 0; i < n; ++i) {
    if (used[i]) {
      continue;
    }
    int v = i;
    int len = 0;
    while (!used[v]) {
      ++len;
      used[v] = true;
      v = p[v];
    }
    cycles.push_back(len);
  }
  sort(cycles.begin(), cycles.end());
  int a = calcMax(cycles, n, k);
  int b = calcMin(cycles, n, k);
  return make_pair(b, a);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &p[i]);
    --p[i];
    ip[p[i]] = i;
  }
  pair<int, int> res = clever(n, k);
  printf("%d %d\n", res.first, res.second);
  return 0;
  for (int n = 1; n <= 10; ++n) {
    cerr << n << endl;
    for (int k = 0; k <= n; ++k) {
      vector<int> a(n);
      for (int i = 0; i < n; ++i) {
        a[i] = i;
      }
      do {
        bool bad = false;
        for (int i = 0; i < n; ++i) {
          p[i] = a[i];
          ip[p[i]] = i;
          if (a[i] == i) {
            bad = true;
          }
        }
        if (bad) {
          continue;
        }
        if (trivial(n, k) != clever(n, k)) {
          for (int j = 0; j < n; ++j) {
            printf("%d ", a[j] + 1);
          }
          printf("\n");
          printf("%d\n", k);
          printf("%d %d\n", trivial(n, k).first, trivial(n, k).second);
          printf("%d %d\n", clever(n, k).first, clever(n, k).second);
          return 0;
        }
      } while (next_permutation(a.begin(), a.end()));
    }
  }
  return 0;
}

```