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>
using namespace std;

const int nmax=1e5+42;

int n,a,b;

vector<int> adj[nmax];

int depth[nmax];

vector<int> seen[nmax];

int d_max=0;

void dfs(int node,int d)
{
    //cout<<"dfs "<<node<<" "<<d<<endl;

    d_max=max(d_max,d);

    depth[node]=d;

    seen[depth[node]].push_back(node);

    for(auto w:adj[node])
        dfs(w,d+1);
}

pair< vector<int>, vector<int> > active[nmax];

void push(int SZ,vector<int> cur)
{
    //cout<<"push "<<SZ<<" cur: ";for(auto w:cur)cout<<w<<" ";cout<<endl;

    if(active[SZ].first.size()==0)
    {
        active[SZ].first=cur;
        return;
    }

    if(active[SZ].second.size()==0)
    {
        active[SZ].second=cur;
        return;
    }

    for(auto w:active[SZ].second)
        cur.push_back(w);

    active[SZ].second={};

    push(2*SZ,cur);
}

bitset<nmax> possible[650];

int pointer=0;

vector<int> mem[nmax];

void add(int SZ,vector<int> cur)
{
    pointer++;

    mem[pointer]=cur;

    //cout<<"add "<<SZ<<" -> ";for(auto w:cur)cout<<w<<" ";cout<<endl;

    possible[pointer]=possible[pointer-1]|(possible[pointer-1]<<SZ);
}

int colour_depth[nmax];

void direct()
{
    while(a)
    {
        if(possible[pointer-1][a])pointer--;
        else
        {
            for(auto w:mem[pointer])
            {
                colour_depth[w]=1;
                a=a-seen[w].size();
            }

            pointer--;
        }
    }

    a=n-b;

    printf("%i\n",d_max);
    for(int i=1;i<=n;i++)
        if(colour_depth[depth[i]])
        {
            printf("a");
            a--;
        }
        else printf("b");

    printf("\n");

    assert(a==0);

    exit(0);
}

char outp[nmax];

set< string > all;

void gaz(int node,string cur)
{
    cur.push_back(outp[node]);

    all.insert(cur);

    for(auto w:adj[node])
        gaz(w,cur);
}
int dumb()
{
    gaz(1,"");

    return all.size();
}

mt19937 rng(42);

int main()
{
    scanf("%i%i",&n,&a);
    /*
    n=200;
    a=100;
    */
    b=n-a;

    for(int i=2;i<=n;i++)
    {
        int p;
        scanf("%i",&p);
        /*
        p=rng()%(i-1)+1;

        if(p<=n/2)p=1;
        */

        adj[p].push_back(i);
    }

    dfs(1,1);

    for(int i=1;i<=d_max;i++)
    {
        push(seen[i].size(),{i});
    }

    possible[0][0]=1;

    for(int i=1;i<=n;i++)
    {
        if(active[i].first.size())add(i,active[i].first);
        if(active[i].second.size())add(i,active[i].second);
    }

    if(possible[pointer][a])
    {
        direct();
        return 0;
    }

    /*
    for(int i=1;i<=d_max;i++)
    {
        cout<<i<<" -> ";
        for(auto w:seen[i])cout<<w<<" ";cout<<endl;
    }
    */

    for(int i=1;i<=d_max;i++)
    {
        if(seen[i].size()<=a)
        {
            a=a-seen[i].size();

            for(auto w:seen[i])
                outp[w]='a';

            continue;
        }

        if(seen[i].size()<=b)
        {
            b=b-seen[i].size();

            for(auto w:seen[i])
                outp[w]='b';

            continue;
        }

        //a, b < seen[i].size()
        vector<int> leaf={},non_leaf={};

        for(int j=1;j<=n;j++)
            if(outp[j]==0&&depth[j]==i)
            {
                if(adj[j].size()==0)leaf.push_back(j);
                else non_leaf.push_back(j);
            }

        //cout<<leaf.size()<<" "<<non_leaf.size()<<endl;

        if(non_leaf.size()<=a)
        {
            for(auto w:non_leaf)
            {
                a--;
                outp[w]='a';
            }

            for(auto w:seen[i])
                if(a&&outp[w]==0)
                {
                    a--;
                    outp[w]='a';
                }
        }
        else
        {
            assert(non_leaf.size()<=b);

            for(auto w:non_leaf)
            {
                b--;
                outp[w]='b';
            }

            for(auto w:seen[i])
                if(b&&outp[w]==0)
                {
                    b--;
                    outp[w]='b';
                }

        }

            for(int w=1;w<=n;w++)
                if(outp[w]==0)
            {
                if(a)
                {
                    a--;
                    outp[w]='a';
                    continue;
                }

                b--;
                outp[w]='b';
            }

        break;
    }

    //cout<<"d_max= "<<d_max<<endl;

    assert(a==0);
    assert(b==0);

    printf("%i\n",d_max+1);
    for(int i=1;i<=n;i++)
        printf("%c",outp[i]);
    printf("\n");

    //cout<<dumb()<<endl;

    //assert(d_max+1==dumb());

    return 0;
}