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>
#define close ios::sync_with_stdio(false)
using namespace std;
const int maxn=1e5+100;
int n,x,maxnum=0,maxdep=0,object_num=0,val[maxn],judge[maxn],deep[maxn],leaf[maxn];
vector<int> G[maxn],depth[maxn],cnt[maxn];
bitset<maxn> b[2100];
void DFS(int root,int dep)
{
	if(dep>maxdep) maxdep=dep;
	deep[root]=dep;
	depth[dep].push_back(root);
	if(G[root].size()==0) leaf[dep]++;
	for(auto cur:G[root]) DFS(cur,dep+1);
}
void Find(int x)
{
	for(int i=object_num;i>0;--i)
	{
		int size=cnt[val[i]].size();
		for(int j=0;j<size;++j){
			if(val[i]>x || b[i-1][x]) break;
			x-=val[i],judge[cnt[val[i]][j]]=1;
		}
	}
}
int main()
{
	close;cin>>n>>x;
	for(int i=2;i<=n;++i){int fa;cin>>fa;G[fa].push_back(i);}
	DFS(1,1);
	for(int i=1;i<=x;++i){
		int size=depth[i].size();
		if(size>maxnum) maxnum=size;
		cnt[size].push_back(i);
	}
	b[object_num][0]=1;
	for(int i=1;i<=maxnum;++i){
		int size=cnt[i].size();
		if(size==0) continue;
		val[++object_num]=i;
		b[object_num]=b[object_num-1];
		for(int j=1;j<=size;j<<=1){
			size-=j;
			b[object_num]|=(b[object_num]<<(i*j));
		}
		if(size>0) b[object_num]|=(b[object_num]<<(i*size));
	}
	if(b[object_num][x]){
		cout<<maxdep<<endl;
		Find(x);
		for(int i=1;i<=n;++i) cout<<(judge[deep[i]]?'a':'b');
	}
	else{
		int res;
		for(int i=x;i>=0;--i){if(b[object_num][i]) {res=i;break;}}
		Find(res);int pos;res=x-res;
		for(int i=1;i<=maxdep;++i)
			if(!judge[i] && leaf[i]>=res) {pos=i;break;}
		cout<<maxdep+1<<endl;
		for(int i=1;i<=n;++i){
			if(judge[deep[i]]) cout<<'a';
			else if(deep[i]==pos && res>0 && G[i].size()==0) cout<<'a',res--;
			else cout<<'b';
		}
	}
}