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 <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
#define ull unsigned long long 
#define dd double
using namespace std;
const int N1=100005; const int M1=455; const int inf=0x3f3f3f3f;

struct EDGE{
int to[N1*2],nxt[N1*2],head[N1],cte;
void ae(int u,int v)
{ cte++; to[cte]=v, nxt[cte]=head[u]; head[u]=cte; }
}e;
int n,D,X,Y,type,pre,cur;
int fa[N1],dep[N1],num[N1],rest[N1],col[N1];
vector<int>nodes[N1];

void dfs(int u)
{
    num[dep[u]]++; D=max(D,dep[u]); nodes[dep[u]].push_back(u);
    for(int j=e.head[u];j;j=e.nxt[j])
    {
        int v=e.to[j];
        dep[v]=dep[u]+1; dfs(v);
    }
    if(!e.head[u]) rest[dep[u]]++;
}
int ok[2][N1],id[N1],from[N1],pos[N1];
int freq[N1],val[N1],used[N1],m; 

void print(int ans)
{
    printf("%d\n",ans);
    for(int i=1;i<=n;i++) printf("%c",(col[i]^type)+'a'); 
    puts(""); 
}
void findway(int ma)
{
    int now=ma,i,j,k,v;
    while(now)
    {
        j=from[now], i=id[now];
        used[val[i]]=(now-j)/val[i];
        now=j;
    }
    for(int i=1;i<=D;i++)
    {
        if(!used[num[i]]) continue;
        for(int j=0;j<nodes[i].size();j++)
        {
            v=nodes[i][j];
            col[v]=0;
        }
        used[num[i]]--;
    }
}
int getx(int fl)
{
    if(fl)
    for(int i=1;i<=D;i++)
    {
        if(!pos[num[i]]) m++, pos[num[i]]=m, freq[m]=1, val[m]=num[i];
        else freq[ pos[num[i]] ]++;
    }
    memset(ok,0,sizeof(ok));
    int now; ok[0][0]=1; pre=0, cur=1;
    for(int i=1;i<=m;i++)
    {
        memcpy(ok[cur],ok[pre],sizeof(ok[cur]));
        for(int k=0;k<val[i];k++)
        {
            now=-1;
            for(int j=k;j<=X;j+=val[i])
            {
                if(ok[pre][j]) now=j;
                else if(now!=-1&& val[i]*freq[i]>=j-now) 
                    ok[cur][j]=1, from[j]=now, id[j]=i;
            }
        }
        swap(cur,pre);
        if(ok[pre][X]) break;
    }
    if(!ok[pre][X]) return 0;
    findway(X); print(D);
    return 1;
}
void fillend()
{
    freq[ pos[num[D]] ]--;
    getx(0); 
    int v;
    for(int x=X-1;x>=max(X-num[D],0);x--) if(ok[pre][x])
    {
        findway(x);
        for(int j=0;j<X-x;j++) 
        {
            v=nodes[D][j];
            col[v]=0;
        }
        break;
    }
    print(D+1);
}
int fillma()
{
    int x=X;
    for(int i=1;i<=D;i++) 
    if(x>=rest[i]&&x<=num[i])
    {
        int re=x-rest[i];
        for(int j=0;j<nodes[i].size();j++)
        {
            int v=nodes[i][j];
            if(e.head[v]) col[v]=0;
            else if(re) col[v]=0, re--;
        }
        print(D+1);
        return 1;
    }else if(x>num[i]){
        for(int j=0;j<nodes[i].size();j++)
        {
            int v=nodes[i][j]; col[v]=0;
        }
        x-=num[i];
    }
    return 0;
}

int main()
{
    scanf("%d%d",&n,&X); Y=n-X; if(X>Y) swap(X,Y), type^=1;
    for(int i=2;i<=n;i++) scanf("%d",&fa[i]), e.ae(fa[i],i);
    dep[1]=1, dfs(1);
    for(int i=1;i<=D;i++) rest[i]=num[i]-rest[i];
    for(int i=1;i<=n;i++) col[i]=1;
    if(getx(1)) return 0;
    int ma=0, k;
    for(int i=1;i<=D;i++) if(num[i]>ma) ma=num[i], k=i;
    fillma();
    // if(!) fillend(); 
    return 0;
}