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:
/* https://codeforces.com/blog/entry/87523 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000

int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int main() {
	static int dd[N], ll[N + 1], qu[N], *qq[N], kk[N], dp[N + 1], dq[N + 1];
	static char ans[N + 1];
	int n, x, y, h, i, d, d_, k, s, cnt;

	scanf("%d%d", &n, &x);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 1; i < n; i++) {
		int p;

		scanf("%d", &p), p--;
		append(p, i);
	}
	for (i = 1; i < n; i++)
		dd[i] = n;
	cnt = 0, qu[cnt++] = 0;
	for (d = 0; d < n && cnt; d++) {
		qq[d] = (int *) malloc(cnt * sizeof *qq[d]), memcpy(qq[d], qu, (kk[d] = cnt) * sizeof *qu);
		cnt = 0;
		for (h = 0; h < kk[d]; h++) {
			int o;

			i = qq[d][h];
			for (o = eo[i]; o--; ) {
				int j = ej[i][o];

				qu[cnt++] = j;
			}
		}
	}
	d_ = d;
	for (d = 0; d < d_; d++)
		ll[kk[d]]++;
	dp[0] = -1;
	for (k = 1; k <= n; k++) {
		if (ll[k] == 0)
			continue;
		for (s = 0; s <= n; s++)
			dq[s] = dp[s] ? 0 : (s >= k && dq[s - k] < ll[k] ? dq[s - k] : ll[k]) + 1;
		for (s = 0; s <= n; s++)
			if (!dp[s] && dq[s] <= ll[k])
				dp[s] = k;
	}
	if (dp[x]) {
		printf("%d\n", d_);
		memset(ll, 0, (n + 1) * sizeof *ll);
		for (k = n, s = x; k >= 1; k--)
			while (dp[s] == k)
				s -= k, ll[k]++;
		for (d = 0; d < d_; d++)
			if (ll[kk[d]]) {
				ll[kk[d]]--;
				for (h = 0; h < kk[d]; h++)
					ans[qq[d][h]] = 'a';
			} else
				for (h = 0; h < kk[d]; h++)
					ans[qq[d][h]] = 'b';
	} else {
		printf("%d\n", d_ + 1);
		y = n - x;
		for (d = 0; d < d_; d++)
			if (x >= kk[d])
				for (h = 0; h < kk[d]; h++)
					ans[qq[d][h]] = 'a', x--;
			else if (y >= kk[d])
				for (h = 0; h < kk[d]; h++)
					ans[qq[d][h]] = 'b', y--;
			else {
				for (h = 0; h < kk[d]; h++) {
					i = qq[d][h];
					if (eo[i])
						ans[i] = 'a', x--;
				}
				for (h = 0; h < kk[d]; h++) {
					i = qq[d][h];
					if (!eo[i]) {
						if (x > 0)
							ans[i] = 'a', x--;
						else
							ans[i] = 'b', y--;
					}
				}
			}
	}
	printf("%s\n", ans);
	return 0;
}