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 JAVA):

Solution:
import java.io.*;
import java.util.*;

/*
polyakoff
*/

public class Main {

    static FastReader in;
    static PrintWriter out;
    static Random rand = new Random();
    static final int oo = (int) 1e9 + 10;
    static final long OO = (long) 2e18 + 10;
    static final int MOD = (int) 1e9 + 7;

    static ArrayList<Integer>[] g;
    static ArrayList<Integer>[] level;

    static void dfs(int v, int depth) {
        level[depth].add(v);
        for (int u : g[v]) {
            dfs(u, depth + 1);
        }
    }

    static void solve() {
        int n = in.nextInt();
        int x = in.nextInt();
        g = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayList<>());
        for (int i = 1; i < n; i++) {
            int p = in.nextInt() - 1;
            g[p].add(i);
        }

        if (n == 1) {
            out.println(1);
            out.println(x == 1 ? 'a' : 'b');
            return;
        }

        level = new ArrayList[n]; Arrays.setAll(level, i -> new ArrayList<>());
        dfs(0, 0);

        int[] cnt = new int[n];
        for (ArrayList<Integer> l : level) {
            cnt[l.size()]++;
        }
        int nLevels = n - cnt[0];

        int[] dp = new int[x + 1];
        int[] dp2 = new int[x + 1];
        int[] last = new int[n];
        int[][] memo = new int[n][];
        int lasti = -1;
        for (int i = 1; i < n; i++) {
            if (cnt[i] == 0)
                continue;
            last[i] = lasti;
            memo[i] = new int[x + 1];
            if (lasti == -1) {
                for (int j = 0; j <= x; j++) {
                    if (j % i == 0 && j / i <= cnt[i])
                        dp[j] = 0;
                    else
                        dp[j] = -1;
                    memo[i][j] = 0;
                }
            } else {
                System.arraycopy(dp, 0, dp2, 0, x + 1);
                for (int j = 0; j <= x; j++) {
                    dp[j] = -1;
                    if (dp2[j] != -1) {
                        dp[j] = 0;
                        memo[i][j] = j;
                    } else if (j >= i && dp[j - i] != -1 && dp[j - i] < cnt[i]) {
                        dp[j] = dp[j - i] + 1;
                        memo[i][j] = j - dp[j] * i;
                    }
                }
            }
            lasti = i;
        }

        if (dp[x] != -1) {
            out.println(nLevels);
            int[] withA = new int[n];
            int i = lasti;
            int j = x;
            while (i != -1) {
                int i2 = last[i];
                int j2 = memo[i][j];
                withA[i] = (j - j2) / i;
                i = i2;
                j = j2;
            }
            char[] ans = new char[n]; Arrays.fill(ans, 'b');
            for (ArrayList<Integer> l : level) {
                if (withA[l.size()] > 0) {
                    withA[l.size()]--;
                    for (int v : l) {
                        ans[v] = 'a';
                    }
                }
            }
            for (int v = 0; v < n; v++) {
                out.print(ans[v]);
            }
            out.println();
            return;
        }

        out.println(nLevels + 1);
        char[] ans = new char[n];
        int m = n, y = x;
        for (ArrayList<Integer> l : level) {
            if (l.size() <= y) {
                for (int v : l) {
                    ans[v] = 'a';
                }
                y -= l.size();
            } else if (l.size() <= m - y) {
                for (int v : l) {
                    ans[v] = 'b';
                }
            } else {
                boolean a = y >= m - y;
                int z = a ? y : m - y;
                for (int v : l) {
                    if (g[v].size() > 0) {
                        ans[v] = a ? 'a' : 'b';
                        z--;
                    }
                }
                for (int v : l) {
                    if (g[v].size() == 0) {
                        if (z > 0) {
                            z--;
                            ans[v] = a ? 'a' : 'b';
                        } else
                            ans[v] = a ? 'b' : 'a';
                    }
                }
                if (a)
                    y = 0;
            }
            m -= l.size();
        }
        for (int v = 0; v < n; v++) {
            out.print(ans[v]);
        }
        out.println();

    }

    public static void main(String[] args) {
        in = new FastReader();
        out = new PrintWriter(System.out);

        int T = 1;
//        T = in.nextInt();
        while (T-- > 0)
            solve();

        out.flush();
        out.close();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        FastReader() {
            this(System.in);
        }
        FastReader(String file) throws FileNotFoundException {
            this(new FileInputStream(file));
        }
        FastReader(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                st = new StringTokenizer(nextLine());
            }
            return st.nextToken();
        }
        String nextLine() {
            String line;
            try {
                line = br.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
            return line;
        }
    }
}