#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
bitset<2000020> f;
int n, k, p[2000020];
int head[2000020], pos;
struct edge {
  int to, next;
} e[2000020];
void add(int a, int b) {
  pos++;
  e[pos].to = b, e[pos].next = head[a], head[a] = pos;
}
int dfn[2000020], low[2000020], sz;
bool in[2000020];
stack<int> S;
int l[2000020], tot;
void tarjan(int u) {
  dfn[u] = low[u] = ++sz;
  S.push(u);
  in[u] = 1;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (in[v])
      low[u] = min(low[u], dfn[v]);
    else {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    }
  }
  if (dfn[u] == low[u]) {
    tot++;
    int num = 0;
    int v;
    do {
      v = S.top();
      S.pop();
      num++;
      in[v] = 0;
    } while (v != u);
    l[tot] = num;
  }
}
int ansl, ansr;
int cnt[2000020];
int main() {
  n = read(), k = read();
  for (int i = 1; i <= n; i++) {
    p[i] = read();
    add(i, p[i]);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) tarjan(i);
  sort(l + 1, l + 1 + tot);
  int kk = k, now = tot;
  for (int i = 1; i <= tot; i++) cnt[l[i]]++;
  f.set(0);
  for (int i = 1; i <= n; i++) {
    if (!cnt[i]) continue;
    int pw = 1;
    for (; pw <= cnt[i]; cnt[i] -= pw, pw <<= 1) f |= f << (i * pw);
    f |= f << (i * cnt[i]);
  }
  ansl = k + !f.test(k);
  int sti = 0;
  for (int i = tot; i && k > 0; i--) {
    int t = l[i] / 2;
    if (k >= t) {
      k -= t, ansr += t * 2;
      sti += l[i] % 2;
    } else
      ansr += k * 2, k = 0;
  }
  if (k) ansr += min(k, sti);
  printf("%d %d\n", ansl, ansr);
}

### 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;
inline int read() {
  int x = 0, f = 1;
  char ch;
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
bitset<2000020> f;
int n, k, p[2000020];
int head[2000020], pos;
struct edge {
  int to, next;
} e[2000020];
void add(int a, int b) {
  pos++;
  e[pos].to = b, e[pos].next = head[a], head[a] = pos;
}
int dfn[2000020], low[2000020], sz;
bool in[2000020];
stack<int> S;
int l[2000020], tot;
void tarjan(int u) {
  dfn[u] = low[u] = ++sz;
  S.push(u);
  in[u] = 1;
  for (int i = head[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (in[v])
      low[u] = min(low[u], dfn[v]);
    else {
      tarjan(v);
      low[u] = min(low[u], low[v]);
    }
  }
  if (dfn[u] == low[u]) {
    tot++;
    int num = 0;
    int v;
    do {
      v = S.top();
      S.pop();
      num++;
      in[v] = 0;
    } while (v != u);
    l[tot] = num;
  }
}
int ansl, ansr;
int cnt[2000020];
int main() {
  n = read(), k = read();
  for (int i = 1; i <= n; i++) {
    p[i] = read();
    add(i, p[i]);
  }
  for (int i = 1; i <= n; i++)
    if (!dfn[i]) tarjan(i);
  sort(l + 1, l + 1 + tot);
  int kk = k, now = tot;
  for (int i = 1; i <= tot; i++) cnt[l[i]]++;
  f.set(0);
  for (int i = 1; i <= n; i++) {
    if (!cnt[i]) continue;
    int pw = 1;
    for (; pw <= cnt[i]; cnt[i] -= pw, pw <<= 1) f |= f << (i * pw);
    f |= f << (i * cnt[i]);
  }
  ansl = k + !f.test(k);
  int sti = 0;
  for (int i = tot; i && k > 0; i--) {
    int t = l[i] / 2;
    if (k >= t) {
      k -= t, ansr += t * 2;
      sti += l[i] % 2;
    } else
      ansr += k * 2, k = 0;
  }
  if (k) ansr += min(k, sti);
  printf("%d %d\n", ansl, ansr);
}

```