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:
/*
    ___                         ______      __                  __
   /   |____  __  ___________ _/ ____/___ _/ /___  ____  ______/ /____
  / /| /_  / / / / / ___/ __ `/ /   / __ `/ __/ / / / / / / __  / ___/
 / ___ |/ /_/ /_/ (__  ) /_/ / /___/ /_/ / /_/ /_/ / /_/ / /_/ (__  )
/_/  |_/___/\__,_/____/\__,_/\____/\__,_/\__/\__, /\__, /\__,_/____/
                                            /____//____/

　　　　　／＞　 フ
　　　　　| 　_　 _|
　 　　　／`ミ _x 彡
　　 　 /　　　 　 |
　　　 /　  ヽ　　 ?
　／￣|　　 |　|　|
　| (￣ヽ＿_ヽ_)_)
　＼二つ

*/

#include <queue>
#include <vector>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MP make_pair
#define ll long long
#define fi first
#define se second
using namespace std;

template <typename T>
void read(T &x) {
    x = 0; bool f = 0;
    char c = getchar();
    for (;!isdigit(c);c=getchar()) if (c=='-') f=1;
    for (;isdigit(c);c=getchar()) x=x*10+(c^48);
    if (f) x=-x;
}

template<typename F>
inline void write(F x, char ed = '\n') {
	static short st[30];short tp=0;
	if(x<0) putchar('-'),x=-x;
	do st[++tp]=x%10,x/=10; while(x);
	while(tp) putchar('0'|st[tp--]);
	putchar(ed);
}

template <typename T>
inline void Mx(T &x, T y) { x < y && (x = y); }

template <typename T>
inline void Mn(T &x, T y) { x > y && (x = y); }

const int N = 200500;
int ne[N<<1], to[N<<1], h[N], tot;
inline void add(int x, int y) {
	ne[++tot] = h[x], to[h[x] = tot] = y;
}

int cnt[N], D[N], mxdep, n, x;
vector<int> vec[N];
#include <bitset>
bitset< 50019 > bit[355], B[355], nw;
int ans[N], col[N], deg[N], bl, S = 350;
void dfs(int x, int dep, int fa) {
	vec[D[x] = dep].push_back(x);
	cnt[dep]++, Mx(mxdep, dep);
	for (int i = h[x]; i; i = ne[i]) 
		if (to[i] != fa) deg[x]++, dfs(to[i], dep + 1, x);
}

int main() {
//	freopen ("hs.in","r",stdin);
//	freopen ("hs.out","w",stdout);
	read(n), read(x);
	for (int i = 2, x;i <= n; ++i) read(x), add(x, i), add(i, x);
	dfs(1, 1, 0);
	char a = 'a', b = 'b';
	if (x + x > n) x = n - x, swap(a, b);
	nw[0] = 1, bit[++bl] = nw;
	for (int i = 1;i <= n; ++i) {
		if (!cnt[i]) break;
		nw |= nw << cnt[i];
		if (i % S == 0) bit[++bl] = nw;
	}
	if (!nw[x]) {
		write(mxdep + 1);
		int spj = 0, y = n - x;
		for (int i = 1;i <= mxdep; ++i) {
			if (cnt[i] <= x) {
				for (auto t: vec[i]) ans[t] = a;
				x -= cnt[i];
				continue;
			}
			if (cnt[i] <= y) {
				for (auto t: vec[i]) ans[t] = b;
				y -= cnt[i];
				continue;
			}
			spj = i;
		}
		char tt = x < y ? a : b; int k = min(x, y);
		for (auto t: vec[spj]) 
			if (!deg[t]) ans[t] = k ? (k -= 1, tt) : (a ^ b ^ tt);
		for (auto t: vec[spj])
			if (!ans[t]) ans[t] = a ^ b ^ tt;
		for (int i = 1;i <= n; ++i) putchar(ans[i]);
		return 0;
	}
	write(mxdep);
	for (int i = bl;i >= 1; --i) {
		int st = (i - 1) * S;
		B[0] = bit[i];
		for (int j = st + 1;j <= st + S; ++j) {
			if (!cnt[j]) break;
			B[j - st] = B[j - 1 - st] | B[j - 1 - st] << cnt[j];
		}
		while (mxdep > st) {
			if (B[mxdep - st][x] && !B[mxdep - st - 1][x]) 
				x -= cnt[mxdep], col[mxdep] = 1;
			--mxdep;
		}
	}
	for (int i = 1;i <= n; ++i) putchar(col[D[i]] ? a : b);
	return 0;
}

/*

9 4
1 2 2 2 2 2 1 2

1 0

*/