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 long long LL;

#define rep(i , l , r) for (int i = (l); i < (r); ++i)

typedef pair < int , int > pii;

#define mp make_pair
#define F first
#define S second

const int MN = 1e5 + 5 , SQ = 500;

int N , X , mx , sz[MN] , dp[SQ][MN] , f[MN];
char c[MN];
vector < pii > v , v2;
vector < int > g[MN] , cur[MN];
pair < int , char > a , b;

inline void go(int i , int j) {
	if (i == (int) v2.size())
		return;
	while (!dp[i + 1][j]) {
		++f[v2[i].first];
		j -= v2[i].first;
	}
	go(i + 1 , j);
}
inline void chkmin(int &x , int y) {
	x = min(x , y);
}
inline void chkmax(int &x , int y) {
	x = max(x , y);
}
inline bool cmp(int u , int v) {
	return sz[u] < sz[v];
}
inline int DFS(int u , int d) {
	chkmax(mx , d);
	cur[d].emplace_back(u); sz[u] = 1;
	for (int v : g[u])
		sz[u] += DFS(v , d + 1);
	return sz[u];
}

int main() {
	 
	 scanf("%d%d" , &N , &X);
	 a = mp(X , 'a'); b = mp(N - X , 'b');
	 if (a > b) swap(a , b);
	 for (int i = 2; i <= N; ++i) {
	 	 int x; scanf("%d" , &x);
	 	 g[x].emplace_back(i);
	 }
	 DFS(1 , 0);
	 for (int i = 0; i <= mx; ++i)
	 	v.emplace_back(mp((int) cur[i].size() , i));
	 sort(v.begin() , v.end());
	 for (int i = 0; i < v.size(); ++i)
	 	 if (i == 0 || v[i].F != v[i - 1].F) 
	 		 v2.emplace_back(mp(v[i].F , 1));
	 	 else
		  	 ++v2.back().second;
	 dp[(int)v2.size()][0] = true;
	 for (int i = (int) v2.size() - 1; i >= 0; --i) {
	 	 int val = v2[i].first , frq = v2[i].second;
	 	 vector < int > last (val , -1);
	 	 for (int j = 0; j <= X; ++j) {
	 	 	 if (dp[i + 1][j] == true)
			   	last[j % val] = j;
			 if (last[j % val] == -1 || ((j - last[j % val]) / val) > frq)
			 	dp[i][j] = false;
			 else 
			 	dp[i][j] = true;	
		 }
	 }
	 if (dp[0][X]) {
	 	 go(0 , a.F);
	 	 for (int i = 1; i <= N; ++i) c[i - 1] = b.S;
	 	 for (int i = 0; i <= mx; ++i) {
	 	 	 if (f[(int) cur[i].size()] == 0) continue;
			 --f[(int) cur[i].size()];	 
			 for (auto x : cur[i])
			 	 c[x - 1] = a.S;
		 } 
		 printf("%d\n" , mx + 1); c[N] = '\0';
		 puts(c);
		 return 0;
	 }
	 printf("%d\n" , mx + 2);
	 for (int i = 0; i <= mx; ++i) {
	 	 sort(cur[i].begin() , cur[i].end() , cmp);
	 	 if (a.F < b.F) swap(a , b);
	 	 while (cur[i].size() > 0 && a.F > 0) {
	 		 c[cur[i].back() - 1] = a.S;
			 cur[i].pop_back();
			 --a.F;	
		 }
		 while (cur[i].size() > 0 && b.F > 0) {
		 	 c[cur[i].back() - 1] = b.S;
		 	 cur[i].pop_back();
		 	 --b.F;
		 } 
	 }
	 c[N] = '\0'; 
	 puts(c);
     return 0; 
}