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;
#define debug(x) cout<<#x<<"="<<x<<endl
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define lb long double
#define rs p<<1|1
#define ls p<<1
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9;
inline ll read()
{
    ll p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=(p<<1)+(p<<3)+(c^48),c=getchar();}
    return f*p;
}

struct Edge{
	int to, nex;
}edge[N*2];
int head[N], tot;

void add(int from,int to)
{
	edge[++ tot].nex = head[from];
	edge[tot].to = to;
	head[from] = tot;
}

vector<int>dep[N];
bool ye[N];
int dp[501][N], cnt[N], a[N], bucket[N];
int totnode, x, n, b[N], k[N];
char ans[N];

void dfs(int now,int step)
{
	n = max(n,step);
	a[step] ++;
	dep[step].push_back(now);
	for(int i = head[now];i;i = edge[i].nex)
	{
		int v = edge[i].to;
		dfs(v,step + 1);
	}
}

void find_path1(int now,int x)
{
	if(now == 0) return;
	else
	{
		for(int i = 0;i <= cnt[b[now]]; i++)
		{
			if(dp[now - 1][x - i * b[now]])
			{
				find_path1(now - 1,x - i * b[now]);
				bucket[b[now]] = i;
				break;
			}
		}
	}
} 

void find_ans()
{
	for(int i = 0;i <= n; i++)
	{
		int siz = (int)dep[i].size();
		if(bucket[siz])
		{
			for(int j = 0;j < siz; j++)
			   ans[dep[i][j]] = 'a';
			bucket[siz] --;
		}
		else
		{
			for(int j = 0;j < siz;j ++)
			   ans[dep[i][j]] = 'b';
		}
	}
}

void solve()
{
    scanf("%d%d",&totnode,&x);
    for(int i = 2;i <= totnode; i++) 
    {
    	int pi; scanf("%d",&pi);
    	add(pi,i);ye[pi] = 1;
	}
	dfs(1,0);
	sort(a,a + n + 1);
	tot = 0;
	for(int i = 0;i <= n; i++)
	{
		if(cnt[a[i]] == 0) b[++ tot] = a[i];
		++ cnt[a[i]];
	}
	dp[0][0] = 1;
	for(int i = 1;i <= tot; i++)
	{
		fill(k,k + totnode + 1,inf);
		for(int j = 0;j <= totnode; j++)
		{
			if(dp[i - 1][j]) 
			{  
			    dp[i][j] = 1;k[j] = 0;
			    continue;
			}
			if(j >= b[i])
			{
				k[j] = min(k[j],k[j - b[i]] + 1);
				if(k[j] <= cnt[b[i]]) dp[i][j] = 1;
			}
		}
	} 
	if(dp[tot][x]) 
	{
		printf("%d\n",n + 1);
		find_path1(tot,x);
		find_ans();
		for(int i = 1;i <= totnode; i++)
	        printf("%c",ans[i]);
	}
	else
	{
		printf("%d\n",n + 2);
		int res = x;
		for(int i = x;i >= 0; i--)
		    if(dp[tot][i]) { res = i;break; }
		find_path1(tot,res);
		find_ans();
		for(int i = 1;i <= totnode; i++)
		    if(ans[i] == 'b') ans[i] = '\0';
        x = x - res;
        int flag = 0;
		for(int i = 0;i <= n; i++)
		{
			if(ans[dep[i][0]] == 'a' || ans[dep[i][0]] == 'b')
			    continue; 
			int siz = dep[i].size();
			int sum = 0;
			for(int j = 0;j < siz; j++)
			   if(!ye[dep[i][j]]) ++ sum;
			if(sum >= x && !flag)
			{
			    for(int j = 0;j < siz; j++)
			    {
			    	if(!ye[dep[i][j]] && x > 0) ans[dep[i][j]] = 'a',x --;
			    	else ans[dep[i][j]] = 'b';
				}
				x = 0;flag = 1;
			}
			else
			{
				for(int j = 0;j < siz; j++)
				    ans[dep[i][j]] = 'b';
			}
		} 
		for(int i = 1;i <= totnode; i++)
	        printf("%c",ans[i]);
	}
}

signed main()
{
	int t = 1;
	while(t --) solve();
}
/*
4 2
1 1 1

*/