#include <bits/stdc++.h>
using namespace std;
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& _p) {
  return os << "(" << _p.first << "," << _p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& _V) {
  bool f = true;
  os << "[";
  for (auto v : _V) {
    os << (f ? "" : ",") << v;
    f = false;
  }
  return os << "]";
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& _S) {
  bool f = true;
  os << "(";
  for (auto s : _S) {
    os << (f ? "" : ",") << s;
    f = false;
  }
  return os << ")";
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& _M) {
  return os << set<pair<T, U>>(_M.begin(), _M.end());
}
const signed long long INF = 1000000100;
const long double EPS = 1e-9;
void read_data() {}
void solve() {}
int P[1000100];
int plecak[1000100];
int ile[1000100];
int kto[1000100];
map<int, int> M;
vector<int> S;
int n;
int find(int k) {
  k = min(k, n - k);
  for (auto m : M) {
    for (int(i) = (0); (i) <= (k); (i)++) {
      if (i + m.first > k) break;
      if (plecak[i + m.first]) continue;
      if (plecak[i] and (kto[i] != m.first or ile[i] < m.second)) {
        plecak[i + m.first] = 1;
        if (kto[i] != m.first) ile[i] = 0;
        kto[i + m.first] = m.first;
        ile[i + m.first] = ile[i] + 1;
      }
    }
  }
  return plecak[k];
}
int main() {
  int k;
  scanf("%d%d", &n, &k);
  for (int(i) = (1); (i) <= (n); (i)++) {
    scanf("%d", &P[i]);
  }
  int doub = 0;
  for (int(i) = (1); (i) <= (n); (i)++) {
    if (P[i]) {
      int r = 0;
      int g = i;
      while (P[g]) {
        r++;
        int pg = g;
        g = P[g];
        P[pg] = 0;
      }
      S.push_back(r);
      M[r]++;
      doub += r / 2;
    }
  }
  plecak[0] = 1;
  printf("%d %d\n", k + 1 - find(k),
         min(n, min(doub, k) * 2 + max(0, k - doub)));
}

### 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>
using namespace std;
template <typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& _p) {
  return os << "(" << _p.first << "," << _p.second << ")";
}
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& _V) {
  bool f = true;
  os << "[";
  for (auto v : _V) {
    os << (f ? "" : ",") << v;
    f = false;
  }
  return os << "]";
}
template <typename T>
ostream& operator<<(ostream& os, const set<T>& _S) {
  bool f = true;
  os << "(";
  for (auto s : _S) {
    os << (f ? "" : ",") << s;
    f = false;
  }
  return os << ")";
}
template <typename T, typename U>
ostream& operator<<(ostream& os, const map<T, U>& _M) {
  return os << set<pair<T, U>>(_M.begin(), _M.end());
}
const signed long long INF = 1000000100;
const long double EPS = 1e-9;
void read_data() {}
void solve() {}
int P[1000100];
int plecak[1000100];
int ile[1000100];
int kto[1000100];
map<int, int> M;
vector<int> S;
int n;
int find(int k) {
  k = min(k, n - k);
  for (auto m : M) {
    for (int(i) = (0); (i) <= (k); (i)++) {
      if (i + m.first > k) break;
      if (plecak[i + m.first]) continue;
      if (plecak[i] and (kto[i] != m.first or ile[i] < m.second)) {
        plecak[i + m.first] = 1;
        if (kto[i] != m.first) ile[i] = 0;
        kto[i + m.first] = m.first;
        ile[i + m.first] = ile[i] + 1;
      }
    }
  }
  return plecak[k];
}
int main() {
  int k;
  scanf("%d%d", &n, &k);
  for (int(i) = (1); (i) <= (n); (i)++) {
    scanf("%d", &P[i]);
  }
  int doub = 0;
  for (int(i) = (1); (i) <= (n); (i)++) {
    if (P[i]) {
      int r = 0;
      int g = i;
      while (P[g]) {
        r++;
        int pg = g;
        g = P[g];
        P[pg] = 0;
      }
      S.push_back(r);
      M[r]++;
      doub += r / 2;
    }
  }
  plecak[0] = 1;
  printf("%d %d\n", k + 1 - find(k),
         min(n, min(doub, k) * 2 + max(0, k - doub)));
}

```