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;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
 
#define F first
#define S second
 
const int MAXN = 1e5 + 10;
const int SQ = 450;
const int INF = 1<<20;

int n, X;
vector<int> g[MAXN], lv[MAXN];
string ans;

void dfs(int u = 0, int d = 0) {
	lv[d].push_back(u);
	for(int v : g[u])
		dfs(v, d+1);
}

void greedy() {
	ans.assign(n, '#');
	int Y = n - X;
	char A = 'a', B = 'b';
	for(int i = 0; i < n; i++) {
		if(X < Y) {
			swap(X, Y);
			A ^= 'a'^'b';
			B ^= 'a'^'b';
		}
		if((int) lv[i].size() <= X) {
			for(int u : lv[i]) {
				ans[u] = A;
			}
			X -= lv[i].size();
		} else {
			for(int u : lv[i]) {
				if(!g[u].empty()) {
					ans[u] = A;
					--X;
				}
			}
			for(int u : lv[i]) {
				if(ans[u] == '#') {
					if(X) {
						ans[u] = A; --X;
					} else {
						ans[u] = B; --Y;
					}
				}
			}
		}
	}
}

int cnt[MAXN];
vector<int> vec[MAXN];
vector<pii> a;
void build() {
	for(int i = 0; i < n; i++) 
		++cnt[lv[i].size()];
	for(int i = 0; i < n; i++)
		vec[lv[i].size()].push_back(i);
	for(int i = 1; i <= n; i++)
		if(cnt[i] > 0)
			a.emplace_back(i, cnt[i]);
}

bool dp[SQ][MAXN];
int nxt[SQ][MAXN];

void get_ans(int i, int j) {
	if(i == (int) a.size()) {
		assert(j == 0);
		return;
	}
	
	auto [x, fr] = a[i];
	get_ans(i + 1, j - x * nxt[i][j]);
	for(int rep = 0; rep < nxt[i][j]; rep++) 
		for(int u : lv[vec[x][rep]]) 
			ans[u] = 'a';
	
}
void solve() {
	cin >> n >> X; ans.resize(n, 'b');
	for(int i = 1; i < n; i++) {
		int p; cin >> p; --p;
		g[p].push_back(i);
	}
	dfs();
	build();
	
	int sz = a.size();
	dp[sz][0] = 1;
	for(int i = sz-1; ~i; --i) {
		auto [x, fr] = a[i];
		for(int j = 0; j <= X; j++) {
			if(dp[i+1][j]) {
				nxt[i][j] = 0;
			} else if(j - x >= 0) {
				nxt[i][j] = nxt[i][j - x] + 1;
			} else {
				nxt[i][j] = INF;
			}
		}
		
		for(int j = 0; j <= X; j++) 
			if(nxt[i][j] <= fr) 
				dp[i][j] = 1;
	}
	int d = n;
	while(lv[d].empty())
		--d;
	++d;
	
	if(dp[0][X])
		get_ans(0, X);
	else
		greedy(), ++d;
		
	cout << d << "\n";
	cout << ans << "\n";
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//cout << fixed << setprecision(6);
	
	int te = 1;	
	//cin >> te;
	for (int w = 1; w <= te; w++){
		//cout << "Case #" << w << ": ";
		solve();
	}
	return 0;
}