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 X first
#define Y second
#define sz(a) (int)a.size()
#define pb push_back

using namespace std;

void solve();

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    //cin >> t;
    while (t--)
        solve();
    return 0;
}

int mxdep[100010];

bitset <45010> dp[45010];

vector <int> g[100010];

vector <int> sl[100010];

int mx;

void dfs(int v, int d, int pr = -1) {
    mx = max(mx, d + 1);
    mxdep[v] = d;
    sl[d].pb(v);
    for (auto u : g[v]) {
        if (u != pr) {
            dfs(u, d + 1, v);
            mxdep[v] = max(mxdep[v], mxdep[u]);
        }
    }
}

bool cmp(int a, int b) {
    return mxdep[a] < mxdep[b];
}

int ans[100010];

void solve() {
    int n, x, y;
    cin >> n >> x;
    int xx = x;
    for (int i = 0; i < n - 1; ++i) {
        cin >> y;
        g[i + 1].pb(y - 1);
        g[y - 1].pb(i + 1);
    }
    dfs(0, 0);
    dp[0][0] = 1;
    if (n - x < x) {
        x = n - x;
    }
    int t = mx;
    for (int i = 1; i <= mx; ++i) {
        if (sz(sl[i - 1]) > x)
            dp[i] = dp[i - 1];
        else
            dp[i] = (dp[i - 1] | (dp[i - 1] << sz(sl[i - 1])));
        if (dp[i][x]) {
            t = i;
            break;
        }
    }
    int k = x;
    while (!dp[t][k])
        k--;
    if (k == x) {
        for (int i = t; i > 0; --i) {
            if (k >= sz(sl[i - 1]) && dp[i - 1][k - sz(sl[i - 1])]) {
                k -= sz(sl[i - 1]);
                for (auto j : sl[i - 1])
                    ans[j] = 1;
            }
        }
        cout << mx << '\n';
        for (int i = 0; i < n; ++i) {
            if (xx != x) {
                if (ans[i] == 1)
                    cout << 'b';
                else
                    cout << 'a';
            } else {
                if (ans[i] == 1)
                    cout << 'a';
                else
                    cout << 'b';
            }
        }
        return;
    } else {
        int kk = k;
        for (int i = t; i > 0; --i) {
            if (k >= sz(sl[i - 1]) && dp[i - 1][k - sz(sl[i - 1])]) {
                k -= sz(sl[i - 1]);
                for (auto j : sl[i - 1])
                    ans[j] = 1;
            }
        }
        int pans = mx;
        for (int j = mx - 1; j >= 0; --j) {
            if (ans[sl[j][0]] == 0 && sz(sl[j]) >= x - kk) {
                int mn = x - kk;
                kk = x;
                vector <int> d;
                for (auto i : sl[j]) {
                    d.pb(i);
                }
                sort(d.begin(), d.end(), cmp);
                for (int i = 0; i < mn; ++i)
                    ans[d[i]] = 1;
                pans += mxdep[d[mn - 1]] - j + 1;
                break;
            }
        }
        cout << pans << endl;
        for (int i = 0; i < n; ++i) {
            if (xx != kk) {
                if (ans[i] == 1)
                    cout << 'b';
                else
                    cout << 'a';
            } else {
                if (ans[i] == 1)
                    cout << 'a';
                else
                    cout << 'b';
            }
        }
    }
}