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 mod 998244353
#define oo 1000000010
const int N = 100010;
const int SQ = 500;
int n , x , p;
vector< int > g[N] , cur[N];

char c[N];

int mx;

vector< pair<int,int> > v , v2;

pair< int , char > a , b;

int sz[N];

bool comp(int u,int v){
	return (sz[u] < sz[v]);
}

int DFS(int node,int d){
	mx = max(mx,d);
	cur[d].push_back(node);
	sz[node] = 1;
	for(int i = 0 ;i < (int)g[node].size();i++)
		sz[node] += DFS(g[node][i] , d + 1);	
	return sz[node];
}

bool dp[SQ][N];

int f[N];

void build_path(int i,int j){
	if(i == (int)v2.size())
		return;
	while(!dp[i + 1][j]){
		f[v2[i].first]++;
		j -= v2[i].first;
	}
	build_path(i + 1 , j);
}

int main(){
	scanf("%d%d",&n,&x);
	a = make_pair(x , 'a');
	b = make_pair(n - x , 'b');
	if(a > b) swap(a , b);
	for(int i = 2 ;i <= n;i++){
		scanf("%d",&p);
		g[p].push_back(i);
	}
	DFS(1 , 0);
	for(int i = 0 ;i <= mx;i++)
		v.push_back(make_pair((int)cur[i].size() , i));
	sort(v.begin(),v.end());
	for(int i = 0 ;i < (int)v.size();i++){
		if(i == 0 || v[i].first != v[i - 1].first)
			v2.push_back(make_pair(v[i].first , 1));
		else
			v2.back().second++;
	}
	dp[(int)v2.size()][0] = true;
	int val , frq;
	for(int i = (int)v2.size() - 1;i >= 0;i--){
		val = v2[i].first;
		frq = v2[i].second;
		vector< int > last(val , -1);
		for(int j = 0 ;j <= a.first;j++){
			if(dp[i + 1][j] == true)
				last[j % val] = j;
			if(last[j % val] == -1 || ((j - last[j % val]) / val) > frq)
				dp[i][j] = false;
			else
				dp[i][j] = true;
		}
	}
	if(dp[0][a.first]){
		build_path(0 , a.first);
		for(int i = 1;i <= n;i++) c[i - 1] = b.second;
		for(int i = 0 ;i <= mx;i++){
			if(f[(int)cur[i].size()] == 0) continue;
			f[(int)cur[i].size()]--;
			for(int j = 0 ;j < (int)cur[i].size();j++)
				c[cur[i][j] - 1] = a.second;
		}
		printf("%d\n",mx + 1);
		c[n] = '\0';
		puts(c);
		return 0;	
	}
	printf("%d\n",mx + 2);
	for(int i = 0 ;i <= mx;i++){
		sort(cur[i].begin(),cur[i].end(),comp);
		if(a.first < b.first) swap(a , b);
		while((int)cur[i].size() > 0 && a.first > 0){
			c[cur[i].back() - 1] = a.second;
			cur[i].pop_back();
			a.first--;
		}
		while((int)cur[i].size() > 0 && b.first > 0){
			c[cur[i].back() - 1] = b.second;
			cur[i].pop_back();
			b.first--;
		}
	}
	c[n] = '\0';
	puts(c);
	return 0;
}