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:
//
//                       _oo0oo_
//                      o8888888o
//                      88" . "88
//                      (| -_- |)
//                      0\  =  /0
//                    ___/`---'\___
//                  .' \\|     |// '.
//                 / \\|||  :  |||// \
//                / _||||| -:- |||||- \
//               |   | \\\  -  /// |   |
//               | \_|  ''\---/''  |_/ |
//               \  .-\__  '-'  ___/-. /
//             ___'. .'  /--.--\  `. .'___
//          ."" '<  `.___\_<|>_/___.' >' "".
//         | | :  `- \`.;`\ _ /`;.`/ - ` : | |
//         \  \ `_.   \_ __\ /__ _/   .-` /  /
//     =====`-.____`.___ \_____/___.-`___.-'=====
//                       `=---='

#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#define ll long long
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define F first
#define S second
#define P pair
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a,b) for(int i=a;i<b;i++)
#define V vector
#define RE return
#define ALL(a) a.begin(),a.end()
#define MP make_pair
#define PB emplace_back
#define PF emplace_front
#define FILL(a,b) memset(a,b,sizeof(a))
#define lwb lower_bound
#define upb upper_bound
#define lc (x<<1)
#define rc ((x<<1)|1)
using namespace std;
int n,x,d[100005],s[100005];
int dp[100005],f[100005],lst[100005],maxi;
V<int> v[100005],it[100005],val[100005];
void dfs(int x) {
	it[d[x]].PB(x);
	gmax(maxi,d[x]);
	for(auto u:v[x]) {
		d[u]=d[x]+1;
		dfs(u);
	}
}
bool ans[100005];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>x;
	FOR(i,2,n) {
		int fa;
		cin>>fa;
		v[fa].PB(i);
	}
	d[1]=1;
	dfs(1);
	FOR(i,1,n) {
		if(!it[i].empty())s[it[i].size()]++,val[it[i].size()].PB(i);
	}
	dp[0]=1;
	FOR(t,1,x) {
		if(!s[t])continue;
		FILL(f,0);
		FOR(i,t,x) {
			if(!dp[i]&&dp[i-t]&&f[i-t]<s[t]) {
				f[i]=f[i-t]+1;
				dp[i]=1;
				lst[i]=val[t][f[i]-1];
			}
		}
	}
	if(dp[x]) {
		int now=x;
		while(now) {
			for(auto u:it[lst[now]])ans[u]=1;
			now=now-it[lst[now]].size();
		}
		cout<<maxi<<'\n';
		FOR(i,1,n) {
			if(ans[i]) {
				cout<<'a';
			} else cout<<'b';
		}
	} else {
		int res=n;
		FOR(i,1,n) {
			if(x>it[i].size()) {
				x-=it[i].size();
				for(auto u:it[i])ans[u]=1;
			} else if(res-x>it[i].size()){
				
			}else {
				int nowc=0,nowt=0;
				for(auto u:it[i]) {
					if(!v[u].empty()) {
						nowc++;
					} else nowt++;
				}
				if(x<=nowt||x>=nowc) {
					if(x>=nowc)for(auto u:it[i]) {
							if(!v[u].empty()) {
								ans[u]=1;
								x--;
							}
						}
					for(auto u:it[i]) {
						if(x&&v[u].empty()) {
							ans[u]=1;
							x--;
						}
					}
				}else{
					x=res-x;
					FOR(j,i,n)for(auto u:it[j])ans[u]=1;
					if(x>=nowc)for(auto u:it[i]) {
							if(!v[u].empty()) {
								ans[u]=0;
								x--;
							}
						}
					for(auto u:it[i]) {
						if(x&&v[u].empty()) {
							ans[u]=0;
							x--;
						}
					}
				}
				break;
			}
			res-=it[i].size();
		}
		cout<<maxi+1<<'\n';
		FOR(i,1,n) {
			if(ans[i]) {
				cout<<'a';
			} else cout<<'b';
		}
	}
	RE 0;
}