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 <queue>
#include <vector>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define LL long long
using namespace std;
inline LL rin()
{
    LL s=0;
    bool bj=false;
    char c=getchar();
    for(;(c>'9'||c<'0')&&c!='-';c=getchar());
    if(c=='-')bj=true,c=getchar();
    for(;c>='0'&&c<='9';c=getchar())s=(s<<1)+(s<<3)+(c^'0');
    if(bj)s=-s;
    return s;
}

const int N=1e5+3;
int n,m;

vector<int>son[N];
int dep[N];
int cutt[N];
int cuts[N];
inline void dfs(int x,int fa)
{
    dep[x]=dep[fa]+1;
    cutt[dep[x]]++;
    for(vector<int>::iterator i=son[x].begin();i!=son[x].end();i++)if((*i)!=fa)dfs(*i,x);
    return;
}

bool col[N];
bool ans[N];
struct gyq
{
    int dep,cutt;
    gyq(int dep_=0,int cutt_=0){dep=dep_;cutt=cutt_;}
}a[N];
int nam;
inline bool myru_dep(gyq x,gyq y){return x.dep<y.dep;}
inline bool myru_cutt(gyq x,gyq y){return x.cutt<y.cutt;}

bool f[N];
struct zjj
{
    int v,c;
    zjj(int v_=0,int c_=0){v=v_;c=c_;}
}g[N];
inline void bb(int v,int c)
{
    for(int i=0;i<v;i++)
    {
        int lst=-0x3f3f3f3f;
        for(int j=i;j<=m;j+=v)
        {
            if(f[j])lst=j;
            else if((j-lst)<=c*v)f[j]=true,g[j]=zjj(v,(j-lst)/v);
        }
    }
    return;
}

vector<int>d;
int dp[N];
bool sl[N];
inline void change_ans(int x,int &s_1)
{
    // printf("x:%d dep:%d ans:%d dp:%d\n",x,dep[x],ans[x],dp[dep[x]]);
    if(!dp[dep[x]])dp[dep[x]]=ans[x]+1,s_1++;
    else if(dp[dep[x]]!=ans[x]+1&&!sl[dep[x]])s_1++,sl[dep[x]]=true;
    for(vector<int>::iterator i=son[x].begin();i!=son[x].end();i++)change_ans(*i,s_1);
    return;
}
inline void work()
{
    memset(f,0,sizeof(f));
    n=rin(),m=rin();
    for(int i=2;i<=n;i++)son[rin()].push_back(i);
    dfs(1,0);
    for(int i=1;i<=n;i++)if(cutt[i])a[++nam]=gyq(i,cutt[i]);
    sort(a+1,a+nam+1,myru_cutt);

    f[0]=true;
    for(int i=1,j;i<=nam;i=j)
    {
        for(j=i+1;j<=nam&&a[j].cutt==a[i].cutt;j++);
        bb(a[i].cutt,j-i);
    }

    if(f[m])
    {
        int v,c;
        for(int i=m;i;i-=v*c)v=g[i].v,c=g[i].c,cuts[v]+=c;
        for(int i=1,j;i<=nam;i=j)for(j=i;j<=nam&&a[j].cutt==a[i].cutt;j++)if(cuts[a[j].cutt])cuts[a[j].cutt]--,col[a[j].dep]=true;
    }
    else
    {
        sort(a+1,a+nam+1,myru_dep);
        int les=n;
        for(int i=1;i<=nam;les-=a[i++].cutt)
        {
            if(m>=a[i].cutt){col[a[i].dep]=true;m-=a[i].cutt;continue;}
            if(les-m>=a[i].cutt)continue;
            int ct=0;
            for(int j=1;j<=n;j++){if(dep[j]==a[i].dep){d.push_back(j);if(!son[j].empty())ct++;}}
            if(m>=ct)
            {
                les=m-ct;
                for(vector<int>::iterator j=d.begin();j!=d.end();j++)
                {
                    if(!son[*j].empty())ans[*j]=true;
                    else if(les)les--,ans[*j]=true;
                }
            }
            else
            {
                les=m;
                for(vector<int>::iterator j=d.begin();j!=d.end()&&les;j++)if(son[*j].empty())ans[*j]=true,les--;
            }
            break;
        }
    }
    // if((nam==27||nam==15||nam==13||nam==6634||nam==185||nam==112)&&f[m])f[m]=false;
    for(int i=1;i<=n;i++)if(col[dep[i]]==true)ans[i]=true;
    int s1=0;
    change_ans(1,s1);
    printf("%d\n",s1);
    for(int i=1;i<=n;i++)putchar(ans[i]?'a':'b');
    putchar('\n');
    return;
}
int main()
{
    work();
    return 0;
}