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 push_back
#define lowbit(x) ((x)&(-(x)))
#define mid ((l+r)>>1)
#define lson rt<<1, l, mid
#define rson rt<<1|1, mid+1, r
#define fors(i, a, b) for(int i = (a); i < (b); ++i)
using namespace std;
int n, d;
const int maxn = 1e5 + 5;
int fa[maxn];
vector<int> g[maxn];
int dep[maxn];
vector<int> f[maxn];
vector<int> h[maxn];
int mxd = 0;
void dfs(int u){
    dep[u] = dep[fa[u]]+1; f[dep[u]].pb(u);
    mxd = max(mxd, dep[u]);
    for(int v: g[u]) dfs(v);
}
int tmp[maxn], dp[maxn], cnt[maxn];
#define P pair<int,int>
vector<P> path;
int ans[maxn];
int main()
{
    cin>>n>>d;
    int C = d;
    fors(i,2,n+1) scanf("%d", &fa[i]), g[fa[i]].pb(i);
    dfs(1);
    fors(i,1,mxd+1){
        int num = f[i].size(); h[num].pb(i);
    }
    memset(dp, -1, sizeof dp);
    dp[0] = 0;
    fors(i,1,n+1){//一层的点数
        if(!h[i].size()) continue;//i个点的
        int num = h[i].size();//有num个i点层
        fors(j,0,C+1) tmp[j] = dp[j];
        for(int j = 0; j < i; ++j){//模数为j j,j+i,j+2i ... j+ki
            int last = -1e9;
            for(int k = 0; j + k*i <= C; ++k){
                int cur = j+k*i;
               // cout<<"i:"<<i<<" j:"<<j<<" k:"<<k<<" last:"<<last<<endl;
                if(~dp[cur]) last = cur;
                else if(last >= cur-num*i){
                    dp[cur] = i;
                    cnt[cur] = (cur-last)/i;
                }
            }
        }
    }
    if(~dp[C]){
        printf("%d\n", mxd);
        int cur = C;
        while(cur){
            fors(i,0,cnt[cur]){
                int dd = h[dp[cur]][i];
                for(int x: f[dd]) ans[x] = 1;
            }
            cur -= cnt[cur]*dp[cur];
        }
    }else{
        printf("%d\n", mxd+1);
        int a = d, b = n-d;
        fors(i,1,mxd+1){
            int num = f[i].size();
            if(a >= num) {for(int x: f[i]) ans[x] = 1; a-=num;}
            else if(b >= num) b -= num;
            else{
                static vector<int> t, le;
                for(int x: f[i]) if(g[x].size()) t.pb(x); else le.pb(x);
                if(t.size() <= a) {//非叶子填a
                        for(int x:t) ans[x] = 1; a -= t.size();
                        for(int x:le){
                            a--; ans[x] = 1; if(a==0) break;
                        }
                        break;
                }
                int ned = num-b;
                for(int x: le){
                    ned--; ans[x] = 1; if(ned == 0) break;
                }
                a -= ned; b = 0;
            }
        }
    }
    fors(i,1,n+1) printf(ans[i]?"a":"b");
	return 0;
}