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>
#define maxn 100086

using namespace std;

int n, m, x, D;
int dep[maxn], tag[maxn];
vector<int> e[maxn];
vector<int> d[maxn];
vector<pair<int, int> > v;
vector<bitset<maxn> > bs; 
int cnt[maxn], ans[maxn];

void dfs(int i){
	d[dep[i]].push_back(i);
	D = max(D, dep[i]);
	for(int j = 0;j < e[i].size();j++){
		int to = e[i][j];
		dep[to] = dep[i] + 1;
		dfs(to);
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 2;i <= n;i++){
		scanf("%d", &x);
		e[x].push_back(i);
		tag[x] = true;
	}
	dfs(1);
	for(int i = 0;i <= D;i++) cnt[d[i].size()]++;
	for(int i = 1;i <= n;i++){
		if(!cnt[i]) continue;
		int x = 1;
		while(cnt[i] - x > 0){
			cnt[i] -= x;
			v.push_back({x * i , i});
			x <<= 1;
		}
		v.push_back({cnt[i] * i, i});
		cnt[i] = 0;
	}
	bitset<maxn> b;
	b.reset(), b[0] = 1;
	bs.push_back(b); 
	for(int i = 0;i < v.size();i++) bs.push_back(bs.back() | (bs.back() << v[i].first));
	if(bs.back()[m]){
		bs.pop_back(), x = m;
		for(int i = v.size() - 1;~i;i--){
			if(x - v[i].first >= 0 && bs.back()[x - v[i].first]){
				cnt[v[i].second] += v[i].first / v[i].second, x -= v[i].first;
			}
			bs.pop_back();
		}
		for(int i = 0;i <= D;i++){
			if(cnt[d[i].size()]){
				cnt[d[i].size()]--;
				for(int j = 0;j < d[i].size();j++) ans[d[i][j]] = 1;
			}
		}
		printf("%d\n", D + 1);
		for(int i = 1;i <= n;i++) printf(ans[i] ? "a" : "b");
		return 0;
	}
	int x = m, y = n - m;
	for(int i = 0;i <= D;i++){
		if(d[i].size() <= x){
			x -= d[i].size();
			for(int j = 0;j < d[i].size();j++) ans[d[i][j]] = 1;
			continue;
		}
		if(d[i].size() <= y){
			y -= d[i].size();
			continue;
		}
		if(x >= y){
			for(int j = 0;j < d[i].size();j++){
				if(tag[d[i][j]]) ans[d[i][j]] = 1, x--;
			}
			for(int j = 0;j < d[i].size() && x;j++){
				if(!tag[d[i][j]]) ans[d[i][j]] = 1, x--;
			}
		}else{
			for(int j = 0;j < d[i].size();j++){
				if(tag[d[i][j]]) ans[d[i][j]] = 1, y--;
			}
			for(int j = 0;j < d[i].size() && y;j++){
				if(!tag[d[i][j]]) ans[d[i][j]] = 1, y--;
			}
			for(int j = 0;j < d[i].size();j++) ans[d[i][j]] ^= 1;
		}
	}
	printf("%d\n", D + 2);
	for(int i = 1;i <= n;i++) printf(ans[i] ? "a" : "b");
}