#include <bits/stdc++.h>
using namespace std;
const float PI = acos(-1.0);
inline bool bit(int mask, int i) { return (mask >> i) & 1; }
void print(const vector<int>& a) {
  for (int i = 0; i < int(((int)(a).size())); ++i) {
    printf("x^%d * %d + ", i, a[i]);
  }
  puts("");
}
struct cd {
  float x, y;
  cd() : x(0), y(0) {}
  cd(float x, float y) : x(x), y(y) {}
  cd(float z) : x(z), y(0) {}
  cd& operator*=(const cd& z) {
    tie(x, y) = make_pair(x * z.x - y * z.y, x * z.y + y * z.x);
    return *this;
  }
  cd operator*(const cd& z) const {
    cd tmp = z;
    tmp *= *this;
    return tmp;
  }
  cd& operator/=(const float& z) {
    x /= z;
    y /= z;
    return *this;
  }
  cd& operator+=(const cd& z) {
    x += z.x;
    y += z.y;
    return *this;
  }
  cd operator+(const cd& z) const {
    cd tmp = z;
    tmp += *this;
    return tmp;
  }
  cd operator-(const cd& z) const { return cd(x - z.x, y - z.y); }
  float real() const { return x; }
  float imag() const { return y; }
};
namespace FFT {
const int B = 20;
const int N = 1 << B;
cd roots[N];
int inv[N];
cd get_root(int k, int n) { return roots[k * (N / n)]; }
void precalc() {
  for (int i = 0; i < int(N); ++i) {
    float ang = i * 2 * PI / N;
    roots[i] = cd(cos(ang), sin(ang));
  }
}
void precalc_inv(int b) {
  int hb = -1;
  inv[0] = 0;
  for (int i = 1; i < (1 << b); ++i) {
    if (bit(i, hb + 1)) {
      ++hb;
    }
    inv[i] = inv[i ^ (1 << hb)] ^ (1 << (b - hb - 1));
  }
}
void fft(cd* a, int b) {
  precalc_inv(b);
  for (int i = 0; i < int(1 << b); ++i) {
    if (i < inv[i]) {
      swap(a[i], a[inv[i]]);
    }
  }
  for (int len = 1; len * 2 <= (1 << b); len *= 2) {
    for (int i = 0; i < (1 << b); i += 2 * len) {
      assert(i + len + len - 1 < (1 << b));
      for (int j = 0; j < int(len); ++j) {
        cd x = a[i + j];
        cd y = a[i + len + j];
        cd r = get_root(j, len * 2);
        a[i + j] = x + r * y;
        a[i + len + j] = x - r * y;
      }
    }
  }
}
void fft_inv(cd* a, int b) {
  fft(a, b);
  for (int i = 0; i < int(1 << b); ++i) {
    a[i] /= 1 << b;
  }
  reverse(a + 1, a + (1 << b));
}
vector<int> mult(vector<int> x, vector<int> y) {
  int b = 0;
  while ((1 << b) < ((int)(x).size()) || (1 << b) < ((int)(y).size())) ++b;
  ++b;
  static cd X[N];
  static cd Y[N];
  for (int i = 0; i < int(1 << b); ++i) {
    X[i] = 0;
    Y[i] = 0;
  }
  for (int i = 0; i < int(((int)(x).size())); ++i) {
    X[i] = x[i];
  }
  for (int i = 0; i < int(((int)(y).size())); ++i) {
    Y[i] = y[i];
  }
  fft(X, b);
  fft(Y, b);
  for (int i = 0; i < int(1 << b); ++i) {
    X[i] *= Y[i];
  }
  fft_inv(X, b);
  vector<int> res;
  for (int i = 0; i < int(1 << b); ++i) {
    int cur = X[i].real() > 0.5;
    res.push_back(cur);
  }
  while (((int)(res).size()) > 1 && res.back() == 0) {
    res.pop_back();
  }
  return res;
}
};  // namespace FFT
const int MAXN = 1e6 + 10;
int n, k;
int p[MAXN];
bool read() {
  if (scanf("%d%d", &n, &k) < 2) {
    return 0;
  }
  for (int i = 0; i < int(n); ++i) {
    scanf("%d", &p[i]);
    --p[i];
  }
  return 1;
}
bool used[MAXN];
bitset<MAXN> can;
void solve() {
  vector<int> lens;
  memset(used, 0, sizeof used);
  for (int i = 0; i < int(n); ++i) {
    if (!used[i]) {
      int cur = 1;
      int j = p[i];
      while (j != i) {
        ++cur;
        used[j] = 1;
        j = p[j];
      }
      lens.push_back(cur);
    }
  }
  vector<int> cnt_lens(n + 1);
  for (int x : lens) cnt_lens[x]++;
  int need_k = min(k, n - k);
  multiset<pair<int, vector<int>>> S;
  for (int i = 1; i <= n; i++)
    if (cnt_lens[i] > 0) {
      vector<int> cur(min(cnt_lens[i] * i + 1, need_k + 1), 0);
      for (int j = 0; j < ((int)(cur).size()); j += i) cur[j] = 1;
      S.insert(make_pair(((int)(cur).size()), cur));
    }
  while (((int)(S).size()) >= 3) {
    auto mn = S.begin()->second;
    S.erase(S.begin());
    auto mn2 = S.begin()->second;
    S.erase(S.begin());
    vector<int> cur = FFT::mult(mn, mn2);
    S.insert(make_pair(((int)(cur).size()), cur));
  }
  bool can_k = 0;
  {
    if (((int)(S).size()) == 1) {
      vector<int> res = S.begin()->second;
      can_k = need_k < ((int)(res).size()) && res[need_k];
    } else {
      assert(((int)(S).size()) == 2);
      vector<int> res1 = S.begin()->second;
      vector<int> res2 = S.rbegin()->second;
      for (int i = 0; i < int(((int)(res1).size())); ++i) {
        int j = need_k - i;
        if (0 <= j && j < ((int)(res2).size()) && res1[i] && res2[j]) {
          can_k = 1;
        }
      }
    }
  }
  if (can_k) {
    printf("%d ", k);
  } else {
    printf("%d ", k + 1);
  }
  int mx = 0;
  for (int len : lens) {
    if (len % 2 == 0) {
      int use = min(k, len / 2);
      mx += use * 2;
      k -= use;
    }
  }
  for (int len : lens) {
    if (len % 2 == 1) {
      int use = min(k, len / 2);
      mx += use * 2;
      k -= use;
    }
  }
  for (int len : lens) {
    if (len % 2 == 1 && k > 0) {
      --k;
      ++mx;
    }
  }
  printf("%d\n", mx);
}
int main() {
  FFT::precalc();
  while (read()) {
    solve();
  }
  return 0;
}

### Prompt

Your task is to create 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;
const float PI = acos(-1.0);
inline bool bit(int mask, int i) { return (mask >> i) & 1; }
void print(const vector<int>& a) {
  for (int i = 0; i < int(((int)(a).size())); ++i) {
    printf("x^%d * %d + ", i, a[i]);
  }
  puts("");
}
struct cd {
  float x, y;
  cd() : x(0), y(0) {}
  cd(float x, float y) : x(x), y(y) {}
  cd(float z) : x(z), y(0) {}
  cd& operator*=(const cd& z) {
    tie(x, y) = make_pair(x * z.x - y * z.y, x * z.y + y * z.x);
    return *this;
  }
  cd operator*(const cd& z) const {
    cd tmp = z;
    tmp *= *this;
    return tmp;
  }
  cd& operator/=(const float& z) {
    x /= z;
    y /= z;
    return *this;
  }
  cd& operator+=(const cd& z) {
    x += z.x;
    y += z.y;
    return *this;
  }
  cd operator+(const cd& z) const {
    cd tmp = z;
    tmp += *this;
    return tmp;
  }
  cd operator-(const cd& z) const { return cd(x - z.x, y - z.y); }
  float real() const { return x; }
  float imag() const { return y; }
};
namespace FFT {
const int B = 20;
const int N = 1 << B;
cd roots[N];
int inv[N];
cd get_root(int k, int n) { return roots[k * (N / n)]; }
void precalc() {
  for (int i = 0; i < int(N); ++i) {
    float ang = i * 2 * PI / N;
    roots[i] = cd(cos(ang), sin(ang));
  }
}
void precalc_inv(int b) {
  int hb = -1;
  inv[0] = 0;
  for (int i = 1; i < (1 << b); ++i) {
    if (bit(i, hb + 1)) {
      ++hb;
    }
    inv[i] = inv[i ^ (1 << hb)] ^ (1 << (b - hb - 1));
  }
}
void fft(cd* a, int b) {
  precalc_inv(b);
  for (int i = 0; i < int(1 << b); ++i) {
    if (i < inv[i]) {
      swap(a[i], a[inv[i]]);
    }
  }
  for (int len = 1; len * 2 <= (1 << b); len *= 2) {
    for (int i = 0; i < (1 << b); i += 2 * len) {
      assert(i + len + len - 1 < (1 << b));
      for (int j = 0; j < int(len); ++j) {
        cd x = a[i + j];
        cd y = a[i + len + j];
        cd r = get_root(j, len * 2);
        a[i + j] = x + r * y;
        a[i + len + j] = x - r * y;
      }
    }
  }
}
void fft_inv(cd* a, int b) {
  fft(a, b);
  for (int i = 0; i < int(1 << b); ++i) {
    a[i] /= 1 << b;
  }
  reverse(a + 1, a + (1 << b));
}
vector<int> mult(vector<int> x, vector<int> y) {
  int b = 0;
  while ((1 << b) < ((int)(x).size()) || (1 << b) < ((int)(y).size())) ++b;
  ++b;
  static cd X[N];
  static cd Y[N];
  for (int i = 0; i < int(1 << b); ++i) {
    X[i] = 0;
    Y[i] = 0;
  }
  for (int i = 0; i < int(((int)(x).size())); ++i) {
    X[i] = x[i];
  }
  for (int i = 0; i < int(((int)(y).size())); ++i) {
    Y[i] = y[i];
  }
  fft(X, b);
  fft(Y, b);
  for (int i = 0; i < int(1 << b); ++i) {
    X[i] *= Y[i];
  }
  fft_inv(X, b);
  vector<int> res;
  for (int i = 0; i < int(1 << b); ++i) {
    int cur = X[i].real() > 0.5;
    res.push_back(cur);
  }
  while (((int)(res).size()) > 1 && res.back() == 0) {
    res.pop_back();
  }
  return res;
}
};  // namespace FFT
const int MAXN = 1e6 + 10;
int n, k;
int p[MAXN];
bool read() {
  if (scanf("%d%d", &n, &k) < 2) {
    return 0;
  }
  for (int i = 0; i < int(n); ++i) {
    scanf("%d", &p[i]);
    --p[i];
  }
  return 1;
}
bool used[MAXN];
bitset<MAXN> can;
void solve() {
  vector<int> lens;
  memset(used, 0, sizeof used);
  for (int i = 0; i < int(n); ++i) {
    if (!used[i]) {
      int cur = 1;
      int j = p[i];
      while (j != i) {
        ++cur;
        used[j] = 1;
        j = p[j];
      }
      lens.push_back(cur);
    }
  }
  vector<int> cnt_lens(n + 1);
  for (int x : lens) cnt_lens[x]++;
  int need_k = min(k, n - k);
  multiset<pair<int, vector<int>>> S;
  for (int i = 1; i <= n; i++)
    if (cnt_lens[i] > 0) {
      vector<int> cur(min(cnt_lens[i] * i + 1, need_k + 1), 0);
      for (int j = 0; j < ((int)(cur).size()); j += i) cur[j] = 1;
      S.insert(make_pair(((int)(cur).size()), cur));
    }
  while (((int)(S).size()) >= 3) {
    auto mn = S.begin()->second;
    S.erase(S.begin());
    auto mn2 = S.begin()->second;
    S.erase(S.begin());
    vector<int> cur = FFT::mult(mn, mn2);
    S.insert(make_pair(((int)(cur).size()), cur));
  }
  bool can_k = 0;
  {
    if (((int)(S).size()) == 1) {
      vector<int> res = S.begin()->second;
      can_k = need_k < ((int)(res).size()) && res[need_k];
    } else {
      assert(((int)(S).size()) == 2);
      vector<int> res1 = S.begin()->second;
      vector<int> res2 = S.rbegin()->second;
      for (int i = 0; i < int(((int)(res1).size())); ++i) {
        int j = need_k - i;
        if (0 <= j && j < ((int)(res2).size()) && res1[i] && res2[j]) {
          can_k = 1;
        }
      }
    }
  }
  if (can_k) {
    printf("%d ", k);
  } else {
    printf("%d ", k + 1);
  }
  int mx = 0;
  for (int len : lens) {
    if (len % 2 == 0) {
      int use = min(k, len / 2);
      mx += use * 2;
      k -= use;
    }
  }
  for (int len : lens) {
    if (len % 2 == 1) {
      int use = min(k, len / 2);
      mx += use * 2;
      k -= use;
    }
  }
  for (int len : lens) {
    if (len % 2 == 1 && k > 0) {
      --k;
      ++mx;
    }
  }
  printf("%d\n", mx);
}
int main() {
  FFT::precalc();
  while (read()) {
    solve();
  }
  return 0;
}

```