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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
int n,gl;
vector<int> g[100009],pos[100009],ds[100009];
int deg[100009],dep[100009],sm[100009];
int vl[100009],rep[100009];
int f[100009],lsp[100009],lsv[100009];
int ans[100009];
int out[100009];
void dfs(int x,int fa)
{
	dep[x]=dep[fa]+1;
	for(int u:g[x])
		if(u!=fa)
			dfs(u,x);
}
int main()
{
	scanf("%d%d",&n,&gl);
	for(int i=2,a;i<=n;i++)
	{
		scanf("%d",&a);
		g[a].pb(i),g[i].pb(a);
		deg[a]++,deg[i]++;
	}
	dfs(1,0);
	int mxd=0;
	for(int i=1;i<=n;i++)
		sm[dep[i]]++,ds[dep[i]].pb(i),mxd=max(mxd,dep[i]);
	for(int i=1;i<=n;i++)
		if(sm[i])
			pos[sm[i]].pb(i);
	map<int,int> mp;
	for(int i=1;i<=n;i++)
		if(sm[i])
			mp[sm[i]]++;
	int tp=0;
	for(auto t:mp)
		vl[++tp]=t.fi,rep[tp]=t.se;
	f[0]=1;
	for(int i=1;i<=tp;i++)
	{
		for(int j=0;j<vl[i];j++)
		{
			int lst=-1;
			for(int k=j;k<=n;k+=vl[i])
			{
				if(f[k])
					lst=k;
				else if(lst!=-1&&(k-lst)/vl[i]<=rep[i])
				{
					f[k]=1;
					lsp[k]=lst;
					lsv[k]=vl[i];
				}
			}
		}
	}
	if(f[gl])
	{
		for(int i=gl;i;i=lsp[i])
		{
			int v=lsv[i];
			int rp=(i-lsp[i])/v;
			for(int j=1;j<=rp;j++)
				ans[pos[v].back()]=1,pos[v].pop_back();
		}
		printf("%d\n",mxd);
		for(int i=1;i<=n;i++)
			printf("%c",ans[dep[i]]?'a':'b');
		return 0;
	}
	int sma=gl,smb=n-gl;
	for(int i=1;i<=mxd;i++)
	{
		if(sm[i]<=sma)
		{
			for(int j:ds[i])
				out[j]=1;
			sma-=sm[i];
			continue;
		}
		if(sm[i]<=smb)
		{
			for(int j:ds[i])
				out[j]=0;
			smb-=sm[i];
			continue;
		}
		int tsm=0;
		for(int j:ds[i])
			if(deg[j]>1)
				tsm++;
		if(tsm<=sma)
		{
			for(int j:ds[i])
				if(deg[j]>1)
					out[j]=1;
			sma-=tsm;
			for(int j:ds[i])
				if(deg[j]==1)
				{
					if(sma)
						out[j]=1,sma--;
					else
						out[j]=0,smb--;
				}
		}
		else
		{
			for(int j:ds[i])
				if(deg[j]>1)
					out[j]=0;
			smb-=tsm;
			for(int j:ds[i])
				if(deg[j]==1)
				{
					if(smb)
						out[j]=0,smb--;
					else
						out[j]=1,sma--;
				}
			continue;
		}
	}
	printf("%d\n",mxd+1);
	for(int i=1;i<=n;i++)
		printf("%c",out[i]?'a':'b');
	return 0;
}