Problem: Kilani and Abd are neighbors for 3000 years, but then the day came and Kilani decided to move to another house. As a farewell gift, Kilani is going to challenge Abd with a problem written by their other neighbor with the same name Abd.

<image>

The problem is:

You are given a connected tree rooted at node 1.

You should assign a character a or b to every node in the tree so that the total number of a's is equal to x and the total number of b's is equal to n - x.

Let's define a string for each node v of the tree as follows: 

  * if v is root then the string is just one character assigned to v: 
  * otherwise, let's take a string defined for the v's parent p_v and add to the end of it a character assigned to v. 



You should assign every node a character in a way that minimizes the number of distinct strings among the strings of all nodes.

Input

The first line contains two integers n and x (1 ≤ n ≤ 10^5; 0 ≤ x ≤ n) — the number of vertices in the tree the number of a's.

The second line contains n - 1 integers p_2, p_3, ..., p_{n} (1 ≤ p_i ≤ n; p_i ≠ i), where p_i is the parent of node i.

It is guaranteed that the input describes a connected tree.

Output

In the first line, print the minimum possible total number of distinct strings.

In the second line, print n characters, where all characters are either a or b and the i-th character is the character assigned to the i-th node.

Make sure that the total number of a's is equal to x and the total number of b's is equal to n - x.

If there is more than one answer you can print any of them.

Example

Input


9 3
1 2 2 4 4 4 3 1


Output


4
aabbbbbba

Note

The tree from the sample is shown below:

<image>

The tree after assigning characters to every node (according to the output) is the following:

<image>

Strings for all nodes are the following: 

  * string of node 1 is: a
  * string of node 2 is: aa
  * string of node 3 is: aab
  * string of node 4 is: aab
  * string of node 5 is: aabb
  * string of node 6 is: aabb
  * string of node 7 is: aabb
  * string of node 8 is: aabb
  * string of node 9 is: aa



The set of unique strings is \{a, aa, aab, aabb\}, so the number of distinct strings is 4.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define fr first
#define sc second
#define pii pair<int, int>
using namespace std;
const int N = 100005;

int n, x, p;
vector<int> to[N], cs[N];
int dep[N], mxdep, sz[N];
int v[N], c[N];
int f[2][N], pre[N], id[N], idx, g[N], col[N], num[N];

void dfs(int u, int depth) {
    dep[u] = depth;
    mxdep = max(mxdep, depth);
    sz[dep[u]]++;
    for (auto v : to[u]) dfs(v, depth+1);
}
int main() {
    scanf("%d%d", &n, &x);
    for (int i = 2; i <= n; i++) {
        scanf("%d", &p);
        to[p].pb(i);
    }
    dfs(1, 1);
    for (int i = 1; i <= mxdep; i++) {
        if (!id[sz[i]]) id[sz[i]] = ++idx;
        ++c[id[sz[i]]];
        cs[sz[i]].pb(i);
        v[id[sz[i]]] = sz[i];
    }

    f[0][0] = 1;
    int zs = 1;
    for (int i = 1; i <= idx; i++) {
        g[0] = 0;
        for (int j = 1; j < v[i]; j++) g[j] = -1;
        for (int j = 0; j <= x; j++) f[zs][j] = 0;
        for (int j = 0; j <= x; j++) {
            if (j >= v[i] && !f[zs^1][j]) {
                f[zs][j] = (g[j%v[i]] != -1 && (j-g[j%v[i]])/v[i] <= c[i]);
                if (f[zs][j]) pre[j] = g[j%v[i]], num[j] = v[i];
            }
            f[zs][j] |= f[zs^1][j];
            if (f[zs^1][j]) g[j%v[i]] = j;
        }
        zs ^= 1;
    }

    if (f[idx&1][x]) {
        printf("%d\n", mxdep);
        while (x) {
            int t = (x-pre[x])/num[x];
            for (int i = 0; i < t; i++)
                col[cs[num[x]][i]] = 1;
            x = pre[x];
        }
        for (int i = 1; i <= n; i++)
            putchar(col[dep[i]] ? 'a' : 'b');
    } else {
        printf("%d\n", mxdep+1);
        int ra = x, rb = n-x, dp, mc, cnt;
        for (int i = 1; i <= mxdep; i++) {
            if (sz[i] <= ra) col[i] = 1, ra -= sz[i];
            else if (sz[i] <= rb) rb -= sz[i];
            else {dp = i, mc = ra < rb, cnt = sz[i]-(ra < rb ? rb : ra); break; }
        }
        for (int i = 1; i <= n; i++)
            if (dep[i] < dp) putchar(col[dep[i]] ? 'a' : 'b');
            else if (dep[i] > dp) putchar(mc ? 'a' : 'b');
            else if (!to[i].size() && cnt) putchar(mc ? 'a' : 'b'), --cnt;
            else putchar(mc ? 'b' : 'a');
    }
        
    return 0;
}