#include <bits/stdc++.h>
using namespace std;
void addmod(int &a, long long b) {
  a = (a + b);
  if (a >= 1000000007) a -= 1000000007;
}
void mulmod(int &a, long long b) { a = (a * b) % 1000000007; }
template <class T>
bool domin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool domax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
int gi() {
  int a;
  scanf("%d", &a);
  return a;
}
long long gll() {
  long long a;
  scanf("%lld", &a);
  return a;
}
class graphal {
 public:
  int n;
  vector<vector<int> > ed;
  graphal(const int &n) : n(n), ed(n) {}
  void reset(int n) {
    ed.clear();
    this->n = n;
    ed.resize(n);
  }
  void add(int a, int b) { ed[a].push_back(b); }
  void load(int m) {
    for (int i = 0; i < m; i++) {
      int a = gi(), b = gi();
      add(a - 1, b - 1);
    }
  }
};
int main() {
  int n = gi(), k = gi();
  graphal g(n);
  vector<bool> vis(n, false);
  for (int i = 0; i < n; i++) {
    int a = gi() - 1;
    g.add(i, a);
  }
  vector<int> sz;
  for (int i = 0; i < n; i++)
    if (!vis[i]) {
      int cnt = 0;
      int ix = i;
      while (!vis[ix]) {
        cnt++;
        vis[ix] = true;
        ix = g.ed[ix][0];
      }
      sz.push_back(cnt);
    }
  int mn = 0, mx = 0, tk = k, od = 0;
  vector<int> tl(1000005, 0);
  for (auto i : sz) {
    tl[i]++;
    if (tk >= i / 2) {
      mx += (i / 2) * 2;
      tk -= i / 2;
      od += (i & 1);
    } else {
      mx += tk * 2;
      tk = 0;
    }
  }
  mx += min(tk, od);
  bitset<1000005> bt;
  bt.set(n);
  for (int i = 1; i < 1000005; i++)
    if (tl[i]) {
      int cnt = tl[i], pt = 1;
      while (cnt) {
        pt = min(pt, cnt);
        int val = pt * i;
        bt |= (bt >> val);
        cnt -= pt;
        pt *= 2;
      }
    }
  mn = k;
  if (!bt.test(k)) {
    mn++;
  }
  cout << mn << " " << mx << endl;
  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;
void addmod(int &a, long long b) {
  a = (a + b);
  if (a >= 1000000007) a -= 1000000007;
}
void mulmod(int &a, long long b) { a = (a * b) % 1000000007; }
template <class T>
bool domin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
bool domax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
int gi() {
  int a;
  scanf("%d", &a);
  return a;
}
long long gll() {
  long long a;
  scanf("%lld", &a);
  return a;
}
class graphal {
 public:
  int n;
  vector<vector<int> > ed;
  graphal(const int &n) : n(n), ed(n) {}
  void reset(int n) {
    ed.clear();
    this->n = n;
    ed.resize(n);
  }
  void add(int a, int b) { ed[a].push_back(b); }
  void load(int m) {
    for (int i = 0; i < m; i++) {
      int a = gi(), b = gi();
      add(a - 1, b - 1);
    }
  }
};
int main() {
  int n = gi(), k = gi();
  graphal g(n);
  vector<bool> vis(n, false);
  for (int i = 0; i < n; i++) {
    int a = gi() - 1;
    g.add(i, a);
  }
  vector<int> sz;
  for (int i = 0; i < n; i++)
    if (!vis[i]) {
      int cnt = 0;
      int ix = i;
      while (!vis[ix]) {
        cnt++;
        vis[ix] = true;
        ix = g.ed[ix][0];
      }
      sz.push_back(cnt);
    }
  int mn = 0, mx = 0, tk = k, od = 0;
  vector<int> tl(1000005, 0);
  for (auto i : sz) {
    tl[i]++;
    if (tk >= i / 2) {
      mx += (i / 2) * 2;
      tk -= i / 2;
      od += (i & 1);
    } else {
      mx += tk * 2;
      tk = 0;
    }
  }
  mx += min(tk, od);
  bitset<1000005> bt;
  bt.set(n);
  for (int i = 1; i < 1000005; i++)
    if (tl[i]) {
      int cnt = tl[i], pt = 1;
      while (cnt) {
        pt = min(pt, cnt);
        int val = pt * i;
        bt |= (bt >> val);
        cnt -= pt;
        pt *= 2;
      }
    }
  mn = k;
  if (!bt.test(k)) {
    mn++;
  }
  cout << mn << " " << mx << endl;
  return 0;
}

```