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 <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = (int) 1e6 + 10;
int p[N], h[N], cnt[N], can[N], w[N], n, a, b, maxh;
char res[N];
bool parent[N], ans[N];
vector<int> who[N], which[N];
vector<vector<bool>> what;

int get(int i) {
	if (i == 0) return 0;
	if (h[i] != -1) return h[i];
	return h[i] = get(p[i]) + 1;
}

int main() {
	scanf("%d%d", &n, &a), b = n - a;
	for (int i = 1; i < n; ++i) {
		scanf("%d", &p[i]), p[i]--;
		parent[p[i]] = true;
	}
	for (int i = 0; i < n; ++i) {
		h[i] = -1;
	}
	for (int i = 0; i < n; ++i) {
		h[i] = get(i);
		cnt[h[i]]++;
		which[h[i]].push_back(i);
		maxh = max(maxh, h[i]);
	}
	for (int i = 0; i <= n; ++i) {
		w[cnt[i]]++;
		who[cnt[i]].push_back(i);
	}
	vector<bool> tmp(n + 1, false);
	tmp[0] = true;
	what.push_back(tmp);
	for (int i = 1; i <= n; ++i) {
		if (w[i] == 0) continue;
		// fprintf(stderr, "%d : %d\n", i, w[i]);
		for (int j = 0; j <= n; ++j) {
			if (what.back()[j]) can[j] = 0;
			else if (j >= i) can[j] = can[j - i] + 1;
			else can[j] = N;
		}
		for (int j = 0; j <= n; ++j) {
			tmp[j] = (can[j] <= w[i]);
			// fprintf(stderr, "%c", "01"[tmp[j]]);
		}
		// fprintf(stderr, "\n");
		what.push_back(tmp);
	}
	if (what.back()[a]) {
		printf("%d\n", maxh + 1);
		for (int i = n; i >= 1; --i) {
			if (w[i] == 0) continue;
			what.pop_back();
			for (int j = 0; (j <= w[i]) && (j * i <= a); ++j) {
				if (what.back()[a - i * j]) {
					// fprintf(stderr, "can take %d copies of %d\n", j, i);
					for (int k = 0; k < j; ++k) {
						ans[who[i][k]] = true;
					}
					a -= i * j;
					break;
				}
			}
		}
		for (int i = 0; i < n; ++i) {
			printf(ans[h[i]] ? "a" : "b");
		}
		printf("\n");
		return 0;
	}
	printf("%d\n", maxh + 2);
	char ca = 'a', cb = 'b';
	for (int i = 0; i <= n; ++i) {
		if (a < b) swap(a, b), swap(ca, cb);
		if (cnt[i] <= a) {
			for (int j : which[i]) {
				res[j] = ca;
			}
			a -= cnt[i];
		} else {
			for (int j : which[i]) {
				if (parent[j]) {
					res[j] = cb;
					--b;
				}
			}
			for (int j : which[i]) {
				if (!parent[j]) {
					if (b > 0) {
						res[j] = cb;
						--b;
					} else {
						res[j] = ca;
						--a;
					}
				}
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		printf("%c", res[i]);
	}
	printf("\n");
	return 0;
}