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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;

const int maxn=100010;

vector<int> ch[maxn];
vector<int> depnodes[maxn];
int fa[maxn];
int dep[maxn];
int maxdep;
int col[maxn];

void dfs(int n)
{
    dep[n] = dep[fa[n]]+1;
    for (int i=0;i<ch[n].size();i++)
        dfs(ch[n][i]);
}

int depcnt[maxn];
vector<int> idxs[maxn];

struct Node
{
    int nxt;
    int idx;
    int beg;
    int end;
};
int dp[maxn];
Node nxt[maxn];

bool best(int n, int m)
{
    memset(dp, 0, sizeof(dp));
    memset(col, 0, sizeof(col));
    for (int i=0;i<=maxdep;i++)
        idxs[i].clear();

    for (int i=1;i<=maxdep;i++)
        idxs[depcnt[i]].push_back(i);

    vector<int> vecidxs;
    for (int i=0;i<maxn;i++)if(idxs[i].size())
        vecidxs.push_back(i);

    dp[0] = 1;
    for (int j=0;j<vecidxs.size();j++)
    {
        int idx = vecidxs[j];
        int size = idxs[idx].size();
        int beg = 0;
        for (int k=0;k<20&&(1<<k)<=size;k++)
        {
            int delta = (1<<k)*idx;
            for (int i=n-1;i>=0;i--)if(dp[i] && !dp[i+delta])
            {
                dp[i+delta] = 1;
                nxt[i+delta] = {i, idx, beg, beg+(1<<k)};
            }
            size -= (1<<k);
            beg += (1<<k);
        }
        if (size)
        {
            for (int i=n-1;i>=0;i--)if(dp[i] && !dp[i+size*idx])
            {
                dp[i+size*idx] = 1;
                nxt[i+size*idx] = {i, idx, beg, beg+size};
            }
        }
    }
    if (dp[m])
    {
        //printf("\t");
        printf("%d\n", maxdep);
        int cur = m;
        while (cur)
        {
            const Node& node = nxt[cur];
            for (int i=node.beg;i<node.end;i++)
            {
                int d = idxs[node.idx][i];
                //printf("%d ", idxs[node.idx][i]);
                for (int j=0;j<depnodes[d].size();j++)
                    col[depnodes[d][j]]=1;
            }
            cur = node.nxt;
        }
        for (int i=1;i<=n;i++)
            printf("%c", col[i]?'a':'b');
        puts("");
    }
    return dp[m];
}

void gao(int n, int m)
{
    for (int i=1;i<=maxdep;i++)
    {
        if (m>=depcnt[i])
        {
            m-=depcnt[i];
            for (int v : depnodes[i])
                col[v] = 1;
        }
        else
        {
            for (int j=maxdep;j>=i;j--)if(m>=depcnt[j+1] && m<depcnt[j])
            {
                for (int v : depnodes[j+1])
                    col[v] = 1;
                m -= depcnt[j+1];
                for (int v : depnodes[j])if(ch[v].empty())
                {
                    if (m<=0)
                        break;
                    col[v] = 1;
                    m--;
                }
                if (m<=0)
                    break;
            }
            break;
        }
    }
    printf("%d\n", maxdep+1);
    for (int i=1;i<=n;i++)
        printf("%c", col[i]?'a':'b');
    puts("");
}

int main()
{
    int n,m;
    scanf("%d%d", &n,&m);
    for (int i=2;i<=n;i++)
    {
        scanf("%d", &fa[i]);
        ch[fa[i]].push_back(i);
    }
    dfs(1);
    for (int i=1;i<=n;i++)
    {
        depcnt[dep[i]]++;
        depnodes[dep[i]].push_back(i);
        maxdep = max(maxdep, dep[i]);
    }
    if (!best(n, m))
        gao(n, m);
}