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 owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
const ll MOD = 998244353;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 100001;
int par[mxN];
vector<int> adj[mxN];
int n, x;
int depth[mxN];
int mxd[mxN];
vector<int> atd[mxN];
vector<int> atl[mxN];
int sz[mxN];
int restore[mxN];
bool knapsack[mxN];
int flip[mxN];
int res[mxN];
void dfs(int u, int p = -1) {
    for(int v: adj[u]) {
        if(v^p) {
            depth[v] = depth[u] + 1;
            dfs(v, u);
            mxd[u] = max(mxd[u], mxd[v]);
        }
    }
    mxd[u] = max(mxd[u], depth[u]);
    atd[depth[u]].senpai(u);
    if(adj[u].size()==0)atl[depth[u]].senpai(u);
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>x;
    owo(i, 1, n) {
        cin>>par[i];
        par[i]--;
        adj[par[i]].senpai(i);
    }
    dfs(0);
    vector<ttgl> lf;
    owo(i, 0, n) {
        if((int)atd[i].size() > 0) {
            sz[(int)atd[i].size()]++;
        }
        if((int)atl[i].size() > 0)lf.senpai({(int)atl[i].size(), i});
    }
    sort(lf.rbegin(), lf.rend());
    vector<ttgl> items; //cnt: weight
    owo(i, 0, n + 1) {
        int num = 1;
        int s = sz[i];
        while(s >= num) {
            items.senpai({num, i});
            s-=num;
            num*=2;
        }
        if(s)items.senpai({s, i});
    }
    memset(restore, -1, sizeof(restore));
    knapsack[0] = 1;
    int mxitem = 0;
    owo(i, 0, items.size()) {
        owo(j, 0, mxitem + 1) {
            int nxt = j + items[i].first * items[i].second;
            if(nxt >= mxN)break;
            if(knapsack[j] == 1 && restore[j]!= i && knapsack[nxt] == 0) {
                knapsack[nxt] = 1;
                restore[nxt] = i;
                mxitem = max(mxitem, nxt);
            }
        }
    }
    ttgl best {INF, -1};
    owo(i, 0, mxN) {
        if(knapsack[i]) {
            best = min(best, {abs(i - x), i});
        }
    }
    int curr = best.second;
    while(curr!=0) {
        int id = restore[curr];
        flip[items[id].second]+=items[id].first;
        curr-=items[id].second*items[id].first;
    }
    vector<int> d(n);
    iota(d.begin(), d.end(), 0);
    if(best.second > x) {
        sort(d.begin(), d.end(), [&](int a, int b) {
            return atl[a].size() > atl[b].size(); 
        });
    }else {
        sort(d.begin(), d.end(), [&](int a, int b) {
            return atl[a].size() < atl[b].size(); 
        });
        
    }
    owo(i, 0, n) {
        //if(atl[d[i]].size() > 0 && x==489)cout<<i<<" "<<atl[d[i]].size()<<"\n";
        if(flip[atd[d[i]].size()] > 0) {
            flip[atd[d[i]].size()]--;
            for(int k: atd[d[i]]) {
                res[k] = 1;
            }
        }
    }
    int bad = 0;
    if(best.first==0) {
        
    }else { //need to flip some leaves
        bad = 1;
        owo(i, 0, lf.size()) {
            if(res[atd[lf[i].second][0]]==0 && best.second < x) { 
                for(int k: atl[lf[i].second]) {
                    res[k] = 1;
                    best.first--;
                    if(best.first==0)break;
                }
                break;
            }else if(res[atd[lf[i].second][0]]==1 && best.second > x) {
                for(int k: atl[lf[i].second]) {
                    res[k] = 0;
                    best.first--;
                    if(best.first==0)break;
                }
                break;
            }
        }
    }
    cout<<(mxd[0] + bad + 1)<<"\n";
    owo(i, 0, n) {
        cout<<(res[i]==1 ? 'a' : 'b');
    }
    return 0;
}