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 ll long long
#define pb push_back
#define pii pair<int,int>
#define mp make_pair
#define fir first
#define sec second
using namespace std;

inline ll read(){
	ll num=0,neg=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')neg=-1;c=getchar();}
	while(isdigit(c)){num=(num<<3)+(num<<1)+c-'0';c=getchar();}
	return num*neg;
}

const int INF=0x3f3f3f3f;
bool flag[100010];
int n,a,siz[100010],mx,depth[100010],tmp[100010],resiz[500];
char col[100010];
vector<int>s[100010],id[100010];
int g[450][100010];bool f[450][100010];

inline void dfs(int u,int dep){
	siz[dep]++,mx=max(mx,dep);
	depth[u]=dep;
	for(int i=0;i<s[u].size();i++) dfs(s[u][i],dep+1);
}

bool cmp1(int x,int y){return depth[x]==depth[y]?s[x].size()>s[y].size():depth[x]<depth[y];}

inline void getpaint(){
	int x=a,y=n-a;char ox='a',oy='b';
	for(int i=1;i<=n;i++) tmp[i]=i;
	sort(tmp+1,tmp+n+1,cmp1);
	vector<int> use;
	for(int dep=1,now=0;dep<=mx;dep++){
		use.clear();
		while(depth[tmp[now+1]]==dep) use.pb(tmp[++now]);
		if(x<y) swap(x,y),swap(ox,oy);
		for(int j=0;j<min((int)use.size(),x);j++) col[use[j]]=ox;
		for(int j=min((int)use.size(),x);j<use.size();j++) col[use[j]]=oy;
		y-=use.size()-min((int)use.size(),x);
		x-=min((int)use.size(),x);
	}
	for(int i=1;i<=n;i++) printf("%c",col[i]);
	return ;
}

int main(){
	n=read(),a=read();
	for(int i=2,x;i<=n;i++) x=read(),s[x].pb(i);
	dfs(1,1);
	for(int i=1;i<=mx;i++) id[siz[i]].pb(i);
	f[0][0]=1;
	int now=1;
	for(int i=1;i<=n;i++) if(id[i].size())
	{
//		printf("Case:%d\n",i);
//		printf("size is %d\n",id[i].size());
		memset(g[now],-INF,sizeof(g[now]));
		resiz[now]=i;
		for(int j=0;j<=a;j++)
		{
			if(f[now-1][j]){
				f[now][j]=1,
				g[now][j]=0;
			}
			else
			{
				if(j>=i) g[now][j]=g[now][j-i]+1;
				if(g[now][j]>=0&&j>=g[now][j]*i&&g[now][j]<=id[i].size()){
					f[now][j]=f[now-1][j-g[now][j]*i];
				}	
				else {
					f[now][j]=0;
					g[now][j]=-INF;
				}
			}
//			printf("%d ",g[now][j]);
		}
//		printf("\n");
		now++;
	}
	now--;
	if(f[now][a])
	{
		for(int v=a;now>=1;now--)
		{
//			printf("%d %d\n",resiz[now],g[now][v]);
			for(int j=0;j<g[now][v];j++) 
				flag[id[resiz[now]][j]]=1;
			v-=g[now][v]*resiz[now];
		}
		printf("%d\n",mx);
		for(int i=1;i<=n;i++) printf(flag[depth[i]]?"a":"b");
		return 0;
	}
	printf("%d\n",mx+1);
	getpaint();
	return 0;
}