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;
namespace Sakurajima_Mai{
	#define ms(a) memset(a,0,sizeof(a))
	#define repi(i,a,b) for(int i=a,bbb=b;i<=bbb;++i)//attention reg int or reg ll ?
	#define repd(i,a,b) for(int i=a,bbb=b;i>=bbb;--i)
	#define reps(s) for(int i=head[s],v=e[i].to;i;i=e[i].nxt,v=e[i].to)
	#define ce(i,r) i==r?'\n':' '
	#define pb push_back 
	#define all(x) x.begin(),x.end()
	#define gmn(a,b) a=min(a,b)
	#define gmx(a,b) a=max(a,b)
	#define fi first
	#define se second   					  
	typedef long long ll;
	typedef unsigned long long ull;
	typedef double db;
	const int infi=2e9;//infi??,????inf????int
	const ll infl=4e18;
	inline ll ceil_div(ll a,ll b){ return (a+b-1)/b; }
	//std::mt19937 rnd(time(0));//std::mt19937_64 rnd(time(0));
}
using namespace Sakurajima_Mai;
namespace Fast_Read{
	inline int qi(){
	    int f=0,fu=1; char c=getchar();
	    while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
	    while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
	    return f*fu;
	}
	inline ll ql(){
		ll f=0;int fu=1; char c=getchar();
	    while(c<'0'||c>'9'){ if(c=='-')fu=-1; c=getchar(); }
	    while(c>='0'&&c<='9'){ f=(f<<3)+(f<<1)+c-48; c=getchar(); }
	    return f*fu;
	}
	inline db qd(){
	    char c=getchar();int flag=1;double ans=0;
	    while((!(c>='0'&&c<='9'))&&c!='-') c=getchar();
	    if(c=='-') flag=-1,c=getchar();
	    while(c>='0'&&c<='9') ans=ans*10+(c^48),c=getchar();
	    if(c=='.'){c=getchar();for(int Bit=10;c>='0'&&c<='9';Bit=(Bit<<3)+(Bit<<1)) ans+=(double)(c^48)*1.0/Bit,c=getchar();}
	    return ans*flag;
	}
}
namespace Read{
	#define si(a) scanf("%d",&a)
	#define sl(a) scanf("%lld",&a)
	#define sd(a) scanf("%lf",&a)
	#define ss(a) scanf("%s",a)
	#define rai(x,a,b) repi(i,a,b) x[i]=qi()
	#define ral(x,a,b) repi(i,a,b) x[i]=ql()
}
namespace Out{
	#define pi(x) printf("%d",x)
	#define pl(x) printf("%lld",x)
	#define ps(x) printf("%s",x)
	#define pc(x) printf("%c",x)
	#define pe() puts("")
}
namespace DeBug{
	#define MARK false
	#define DB if(MARK) 
	#define pr(x) cout<<#x<<": "<<x<<endl
	#define pra(x,a,b) cout<<#x<<": "<<endl; \
			repi(i,a,b) cout<<x[i]<<" ";	 \
			puts("");   
	#define FR(a) freopen(a,"r",stdin)
	#define FO(a) freopen(a,"w",stdout)
}
using namespace Fast_Read;
using namespace Read;
using namespace Out;
using namespace DeBug;
const int MAX_N=1e5+5;
int n,x;
vector<int> g[MAX_N];
int mxdep=0,deep[MAX_N];

map<int,int> h;
int htot=0;
vector<int> rec[MAX_N],rec2[MAX_N];
int val[MAX_N];
void dfs(int u)
{
	gmx(mxdep,deep[u]),rec[deep[u]].pb(u);
	for(auto v:g[u]) deep[v]=deep[u]+1,dfs(v);
}
bitset<MAX_N> dp[500];
bool ans[MAX_N];
void Reduction(int num,int left)
{
	if(!num) return ;
	for(auto x:rec2[num]){
		if(dp[num-1][left]) break;
		left-=val[num];
		for(auto v:rec[x]) ans[v]=true;
	}
	Reduction(num-1,left);
}
int main()
{
	n=qi(),x=qi();
	repi(i,2,n) g[qi()].pb(i); 
	deep[1]=1; dfs(1);
	
	repi(i,1,mxdep){
		int siz=rec[i].size();
		if(!h[siz]) h[siz]=++htot,val[htot]=siz;
		rec2[h[siz]].pb(i);
	}
	dp[0][0]=1;
	repi(i,1,htot){
		dp[i]=dp[i-1];
		int siz=rec2[i].size();
		for(int j=1;j<=siz;j<<=1) dp[i]|=dp[i]<<(j*val[i]),siz-=j;
		if(siz) dp[i]|=dp[i]<<(siz*val[i]);
	}
	if(dp[htot][x]) pi(mxdep),pe(),Reduction(htot,x);
	else{
		pi(mxdep+1),pe();
		int undetermined=n;
		repi(i,1,mxdep){
			if(rec[i].size()<=x){
				for(auto v:rec[i]) ans[v]=true;
				x-=rec[i].size();
			}
			else if(rec[i].size()<=undetermined-x) ;
			else{
				int mn=min(x,undetermined-x);
				bool mark=x>(undetermined-x);
				vector<int> leaf;
				for(auto v:rec[i]){
					if(!g[v].size()&&mn){
						ans[v]=!mark,mn--;
						if(!mark) x--;
					} 
					else{
						 ans[v]=mark;
						 if(mark) x--;
					}
				}
			}
			undetermined-=rec[i].size();
		}
	}
	repi(i,1,n) pc(ans[i]?'a':'b'); pe();
	return 0;
}