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>

using namespace std;

typedef pair <int, int> pii;

int N, X;
vector <int> ch[100005];
int dep[100005], maxdep;

char flag='a';
char ans[100005];

// 深度为x的节点有哪些
vector <int> depids[100005], depye[100005], depjing[100005];

//////////

vector <int> cntall[100005];
int dataall[100005], NN;

bitset <50002> dp[500], dpf[500];

void dfs(int u, int d) {
    dep[u]=d;
    maxdep=max(maxdep, d);
    depids[d].push_back(u);
    if(ch[u].empty()) depye[d].push_back(u);
    else depjing[d].push_back(u);
    for(auto v : ch[u]) dfs(v, d+1);
}

int cans[100005];

void showAns() {
    for(int i=NN, x=X; i>=1; --i) {
        int v=dataall[i];
        int c=cntall[v].size();

        cans[v]=-1;
        for(int j=0; j<=c && x>=0; ++j, x-=v)
            if(dp[i-1][x]) {
                cans[v]=j;
                break;
            }
        if(cans[v]==-1) cout<<"NO2\n";
        assert(cans[v]!=-1);
    }
    for(int i=1; i<=maxdep; ++i)
        if(cans[depids[i].size()]) {
            --cans[depids[i].size()];
            for(auto u : depids[i]) ans[u]=flag;
        }

    for(int i=1; i<=N; ++i)
        if(!ans[i]) ans[i]=(!(flag-'a'))+'a';
    ans[N+1]=0;
    puts(ans+1);
}

bitset <50002> mdp, mdp2;
int near[100005];

void mergeDP(const bitset <50002> & a, const bitset <50002> & b, int v, int c) {
    mdp.reset();
    if(a.count()>b.count()) {
        for(int i=0; i<=X; ++i)
            if(b[i]) mdp|=a<<i;
    }
    else {
        for(int i=0; i<=X; ++i)
            if(a[i]) mdp|=b<<i;
    }
    mdp2=mdp;
    for(int i=1; i<=c; ++i) mdp|=mdp<<v;
}

void getAns1(int val, int NN) {
    for(int i=NN, x=val; i>=1; --i) {
        int v=dataall[i];
        int c=cntall[v].size();
        bool ok=0;
        for(int j=0; j<=c && x>=0; ++j, x-=v)
            if(dp[i-1][x]) {
                for(int k=0; k<j; ++k)
                    for(auto u : depids[cntall[v][k]])
                        ans[u]=flag;
                ok=1;
                break;
            }
        if(!ok) cout<<"NO3\n";
        assert(ok);
    }
}

void getAns2(int val, int pos) {
    for(int i=pos, x=val; i<=NN; ++i) {
        int v=dataall[i];
        int c=cntall[v].size();
        bool ok=0;
        for(int j=0; j<=c && x>=0; ++j, x-=v)
            if(dpf[i+1][x]) {
                for(int k=0; k<j; ++k)
                    for(auto u : depids[cntall[v][k]])
                        ans[u]=flag;
                ok=1;
                break;
            }
        if(!ok) cout<<"NO4\n";
        assert(ok);
    }
}

bool check(int pos) {
    mdp.reset();
    auto & a=dp[pos-1];
    {
        int v=dataall[pos];
        int c=int(cntall[v].size())-1;
        for(int j=0; j<v; ++j) {
            int jin=-1;
            for(int k=j; k<=X; k+=v) {
                if(a[k]) jin=k;
                if(jin>=0 && jin>=k-c*v) mdp.set(k);
            }
        }
    }
    auto & b=dpf[pos+1];

    int min1=-1, min2=-1;
    for(auto dep : cntall[dataall[pos]]) {
        if(min1==-1 || X-int(depye[dep].size())<X-int(depye[min1].size())) min1=dep;
        if(min2==-1 || X-int(depye[dep].size())-int(depjing[dep].size())<X-int(depye[min2].size())-int(depjing[min2].size())) min2=dep;
    }

    for(int i=0, j=X; i<=X; ++i) {
        if(mdp[i]==0) continue;
        while(j>=0 && i+j>X) --j;
        while(j>=0 && b[j]==0) --j;
        if(j<0) break;
        if(i+j>=X-int(depye[min1].size())) {
            for(int k=0; k<X-i-j; ++k)
                ans[depye[min1][k]]=flag;

            bool ok=0;
            int v=dataall[pos];
            int c=int(cntall[v].size())-1;
            for(int k=0; k<=c; ++k)
                if(i-k*v>=0 && a[i-k*v]) {
                    ok=1;
                    getAns1(i-k*v, pos-1);
                    for(int t=0; t<k;)
                        if(cntall[v][t]!=min1) {
                            for(auto u : depids[cntall[v][t]]) ans[u]=flag;
                            ++t;
                        }
                    break;
                }
            if(!ok) cout<<"NO9\n";
            assert(ok);

            getAns2(j, pos+1);
            for(int k=1; k<=N; ++k)
                if(!ans[k]) ans[k]=(!(flag-'a'))+'a';
            ans[N+1]=0;
            puts(ans+1);
            return 1;
        }
    }

    /*
    int XX=X-int(depjing[min2].size());
    for(int i=0, j=XX; i<=XX; ++i) {
        if(mdp[i]==0) continue;
        while(j>=0 && i+j>XX) --j;
        while(j>=0 && b[j]==0) --j;
        if(j<0) break;
        if(i+j>=X-int(depye[min2].size())-int(depjing[min2].size())) {
            for(auto u : depjing[min2]) ans[u]=flag;
            for(int k=0; k<XX-i-j; ++k)
                ans[depye[min2][k]]=flag;

            bool ok=0;
            int v=dataall[pos];
            int c=int(cntall[v].size())-1;
            for(int k=0; k<=c; ++k)
                if(i-k*v>=0 && a[i-k*v]) {
                    ok=1;
                    getAns1(i-k*v, pos-1);
                    for(int t=0; t<k;)
                        if(cntall[v][t]!=min2) {
                            for(auto u : depids[cntall[v][t]]) ans[u]=flag;
                            ++t;
                        }
                    break;
                }
            if(!ok) cout<<"NO10\n";
            assert(ok);

            getAns2(j, pos+1);
            for(int k=1; k<=N; ++k)
                if(!ans[k]) ans[k]=(!(flag-'a'))+'a';
            ans[N+1]=0;
            puts(ans+1);
            return 1;
        }
    }
    */

    return 0;
}

int main() {
    scanf("%d %d", &N, &X);
    if(X>N-X) X=N-X, flag='b';
    for(int i=2; i<=N; ++i) {
        int p;
        scanf("%d", &p);
        ch[p].push_back(i);
    }
    dfs(1, 1);

    for(int i=1; i<=maxdep; ++i)
        cntall[depids[i].size()].push_back(i);
    for(int i=1; i<=N; ++i)
        if(cntall[i].size())
            dataall[++NN]=i;

    if(NN>=500) cout<<"NO8\n";
    assert(NN<500);

    dp[0].set(0);
    for(int i=1; i<=NN; ++i) {
        int v=dataall[i];
        int c=cntall[v].size();
        for(int j=0; j<v; ++j) {
            int jin=-1;
            for(int k=j; k<=X; k+=v) {
                if(dp[i-1][k]) jin=k;
                if(jin>=0 && jin>=k-c*v) dp[i].set(k);
            }
        }
    }

    if(dp[NN][X]) {
        printf("%d\n", maxdep);
        showAns();
        return 0;
    }

    dpf[NN+1].set(0);
    for(int i=NN; i>=1; --i) {
        int v=dataall[i];
        int c=cntall[v].size();
        for(int j=0; j<v; ++j) {
            int jin=-1;
            for(int k=j; k<=X; k+=v) {
                if(dpf[i+1][k]) jin=k;
                if(jin>=0 && jin>=k-c*v) dpf[i].set(k);
            }
        }
    }

    printf("%d\n", maxdep+1);
    vector <pii> tmp;

    for(int i=NN; i>=1; --i)
        if(check(i)) return 0;

    cout<<"NO1\n";
    assert(1==0);

    return 0;
}