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:
// Problem: F. AB Tree
// Contest: Codeforces - Codeforces Round #699 (Div. 2)
// URL: https://codeforces.com/contest/1481/problem/F
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>

template <typename Tp>
void read(Tp &res){
	static char ch; ch = getchar(), res = 0;
	static bool flag; flag = 0;
	while(!isdigit(ch)) flag = (ch == '-'), ch = getchar();
	while(isdigit(ch)) res = res * 10 + ch - 48, ch = getchar();
	if(flag) res = -res;
}

const int maxn = 1e5 + 19, maxb = 500;

int n, x, cnt[maxn], val[maxn], sz[maxn], dep[maxn], d, tot, okpos[maxn], pre[maxb][maxn], st[maxn], top;
std::vector<int> G[maxn], common[maxn], leaf[maxn];
bool dp[maxb][maxn];
char s[maxn];

inline void add(int a, int b){G[a].push_back(b); }

void dfs(int node){
	++cnt[dep[node]], d = std::max(d, dep[node]);
	if(G[node].size()) common[dep[node]].push_back(node);
	else leaf[dep[node]].push_back(node);
	for(int e : G[node])
		dep[e] = dep[node] + 1, dfs(e);
}

int main(){
	read(n), read(x);
	for(int i = 2, p; i <= n; ++i){
		read(p);
		add(p, i);
	}
	dfs(1);
	for(int i = 0; i <= d; ++i) val[++tot] = cnt[i];
	std::sort(val + 1, val + 1 + tot), tot = std::unique(val + 1, val + 1 + tot) - val - 1;
	for(int i = 0; i <= d; ++i) ++sz[std::lower_bound(val + 1, val + 1 + tot, cnt[i]) - val];
	dp[0][0] = 1;
	for(int i = 1; i <= tot; ++i){
		for(int j = 0; j < val[i]; ++j) okpos[j] = -1e9;
		okpos[0] = 0;
		for(int j = 0; j <= n; ++j){
			if(dp[i - 1][j]) okpos[j % val[i]] = j;
			if(j <= okpos[j % val[i]] + sz[i] * val[i]) dp[i][j] = 1, pre[i][j] = okpos[j % val[i]];
		}
	}
	if(dp[tot][x]){
		printf("%d\n", d + 1);
		static int take[maxn];
		for(int i = tot, v = x; i >= 1; --i){
			take[val[i]] = (v - pre[i][v]) / val[i];
			v = pre[i][v];
		}
		for(int i = 0; i <= d; ++i){
			for(int j : common[i]) st[++top] = j;
			for(int j : leaf[i]) st[++top] = j;
			char c = 'b';
			if(take[top]) --take[top], c = 'a';
			while(top) s[st[top--]] = c;
		}
	}
	else{
		printf("%d\n", d + 2);
		int corcnt[2] = {x, n - x};
		for(int i = 0; i <= d; ++i)
			if(corcnt[0] >= cnt[i] || corcnt[1] >= cnt[i]){
				for(int j : common[i]) st[++top] = j;
				for(int j : leaf[i]) st[++top] = j;
				char c = 'b';
				if(corcnt[0] >= cnt[i]) c = 'a', corcnt[0] -= cnt[i];
				else corcnt[1] -= cnt[i];
				while(top) s[st[top--]] = c;
			}
			else{
				if(corcnt[0] >= (int)common[i].size()){corcnt[0] -= common[i].size(); for(int j : common[i]) s[j] = 'a'; }
				else{corcnt[1] -= common[i].size(); for(int j : common[i]) s[j] = 'b'; }
				for(int j : leaf[i]) st[++top] = j;
				if(corcnt[0] <= top){while(corcnt[0]) --corcnt[0], s[st[top--]] = 'a'; }
				else{while(corcnt[1]) --corcnt[1], s[st[top--]] = 'b'; }
				if(corcnt[0]){
					corcnt[0] -= top;
					while(top) s[st[top--]] = 'a';
				}
				else{
					corcnt[1] -= top;
					while(top) s[st[top--]] = 'b';
				}
			}
	}
	puts(s + 1);
}