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 <ext/pb_ds/assoc_container.hpp>
 #include <ext/pb_ds/priority_queue.hpp>

 using namespace __gnu_pbds;


__gnu_pbds::priority_queue<int, less<int>> pq;
gp_hash_table<int, int> mp;
*/

/** Begin fast allocation */
/*
const int mx_MEM = 10 * 1e7;
int mpos = 0;
char mem[mx_MEM];

inline void *operator new(size_t n) {
    assert((mpos += n) <= mx_MEM);
    return (void *) (mem + mpos - n);
}

inline void operator delete(void *) noexcept {} // must have!
*/
/** End fast allocation */

/** Pragmas */
// mt19937 gen(2281337);

//#pragma GCC optimize("O3", "Ofast", "unroll-loops", "unswitch-loops", "fast-math", "no-stack-protector")

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,abm,mmx,avx")
// sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,abm,mmx,
//#pragma comment(linker, "/STACK:66777216")

/*
 * @author kamil.sharipov
 */

#include <bits/stdc++.h>

//#define int long long
#define all(x) (x).begin(), (x).end()
#define fo(i, a, b) for (int i = a; i < b; ++i)
#define ll long long
#define pii pair<int, int>

using namespace std;

int n, x;
vector<int> p, ans;

vector<vector<int> > a, b, adj, wei, dp;

int lvl_max = 0;

void dfs(int v, int l) {
    lvl_max = max(lvl_max, l + 1);
    for (int i = 0; i < adj[v].size(); ++i) {
        dfs(adj[v][i], l + 1);
    }
    if (adj[v].size() == 0) {
        b[l].push_back(v);
    } else {
        a[l].push_back(v);
    }
}

void add(int lvl) {
    if (x == 0) return;
    for (int i = 0; i < a[lvl].size(); ++i) {
        ans[a[lvl][i]] = 1;
        x--;
    }
    for (int i = 0; i < b[lvl].size(); ++i) {
        if (x == 0) return;
        ans[b[lvl][i]] = 1;
        x--;
    }
}

signed main() {
#ifdef _LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    cin >> n >> x;

    int st = x;

    p.resize(n), ans.resize(n);
    adj.resize(n), a.resize(n), b.resize(n), wei.resize(n + 1);

    for (int i = 0; i < n - 1; ++i) {
        cin >> p[i];
        p[i]--;
        adj[p[i]].push_back(i + 1);
    }

    dfs(0, 0);

    for (int i = 0; i < n; ++i) {
        if (a[i].size() + b[i].size() != 0) {
            wei[a[i].size() + b[i].size()].push_back(i);
        }
    }

    dp.push_back(vector<int>(n + 1));
    vector<int> ras;

    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        if (wei[i].size() != 0) {
            ras.push_back(i);
            vector<int> sm(i, 0);
            vector<int> cur(n + 1, 0);
            cur[0] = 1;

            int sz = wei[i].size();

            for (int j = 0; j <= n; ++j) {
                sm[j % i] += dp[dp.size() - 1][j];

                int lst = j - (sz + 1) * i;
                if (lst >= 0) sm[j % i] -= dp[dp.size() - 1][lst];

                if (sm[j % i] != 0) cur[j] = 1;
            }
            dp.push_back(cur);
        }
    }

    int cnt = lvl_max;
    // copy

    if (dp[dp.size() - 1][x] == 0) {
        cnt++;
        for (int i = 0; i < n; ++i) {
            if (x == 0) break;

            if (a[i].size() <= x) {
                add(i);
            }
        }


    } else {

        for (int i = dp.size() - 1; i > 0; --i) {
            int cur_wei = ras[i - 1];
            for (int j = 0; j <= wei[cur_wei].size(); ++j) {
                if (dp[i - 1][x] == 1) {
                    break;
                }
                add(wei[cur_wei][j]);
            }
        }
    }

    cout << cnt << "\n";
    for (int i = 0; i < n; ++i) {
        if (ans[i] == 1) cout << 'a';
        else cout << 'b';
    }
}