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<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<array>
#include<queue>
#include<set>
using namespace std;

#define imax(a,b) (((a)>(b))?(a):(b))
#define imin(a,b) (((a)<(b))?(a):(b))
#define mp make_pair

typedef long long ll;

const int N = 1e5 + 10;
const int inf = 1e9 + 7;

int n, k, td, tg;
int h[N], ne[N], to[N], tt;
int fa[N], sz[N], cs[N];
int dp[500][N];
vector<int> cur[N];
struct dop
{
	int val, s;
} g[N];
vector<pair<int, int>> V;
char ans[N];

void read(int& x)
{
	x = 0; char ch = getchar(); bool f = 0;
	while (!(ch >= '0' && ch <= '9')) f |= (ch == '-'), ch = getchar();
	while ((ch >= '0' && ch <= '9')) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
	if (f) x = -x;
}

/*ll Mul(ll x, ll y, ll mods)
{
	ll s = 0;
	for (; y; y >>= 1, x = (x << 1) % mods)
		if (y & 1) s = (s + x) % mods;
	return s;
}

ll Pow(ll x, ll y, ll mods)
{
	ll s = 1;
	for (; y; y >>= 1, x = Mul(x, x, mods))
		if (y & 1) s = Mul(s, x, mods);
	return s;
}

ll gcd(ll x, ll y) { return (y ? gcd(y, x % y) : x); }
*/

void addedge(int a, int b)
{
	to[++tt] = b; ne[tt] = h[a]; h[a] = tt;
}

int dfs(int x, int d)
{
	td = imax(td, d); fa[d]++;
	cur[d].push_back(x); sz[x] = 1;
	for (int p = h[x];p;p = ne[p]) sz[x] += dfs(to[p], d + 1);
	return sz[x];
}

bool cmp(int a, int b) { return sz[a] < sz[b]; }

int main()
{
	read(n); read(k); tt = 1;
	pair<int, char> A(k, 'a'), B(n - k, 'b');
	td = 0;  tg = 0;
	for (int i = 2;i <= n;++i) read(fa[i]), addedge(fa[i], i);
	for (int i = 0;i <= n;++i) fa[i] = 0;
	dfs(1, 0);
	for (int i = 0;i <= td;++i) cs[fa[i]]++;
	for (int i = 1;i <= n;++i)
		if (cs[i]) V.push_back(mp(i, cs[i]));
	dp[(int)V.size()][0] = 1;
	int val = 0, frq = 0, * last = cs;
	for (int i = (int)V.size() - 1;i >= 0;--i)
	{
		val = V[i].first; frq = V[i].second;
		for (int j = 0;j <= val;++j) last[j] = -1;
		for (int j = 0;j <= A.first;++j)
		{
			if (dp[i + 1][j]) last[j % val] = j;
			if (last[j % val] == -1 || ((j - last[j % val]) / val) > frq) dp[i][j] = 0;
			else dp[i][j] = 1;
		}
	}
	if (dp[0][A.first])
	{
		printf("%d\n", td + 1);
		for (int i = 0;i <= n;++i) cs[i] = 0;
		int Vs = V.size(), j = A.first;
		for (int i = 0;i < Vs;++i)
		{
			while (!dp[i + 1][j])
			{
				j -= V[i].first;
				cs[V[i].first]++;
			}
		}
		for (int i = 0;i <= td;++i)
		if(cs[fa[i]])
		{
			cs[fa[i]]--;
			for (j = cur[i].size() - 1;j >= 0;--j) ans[cur[i][j] - 1] = A.second;
		}
		else for (j = cur[i].size() - 1;j >= 0;--j) ans[cur[i][j] - 1] = B.second;
		ans[n] = '\0';
		puts(ans);
	}
	else
	{
		printf("%d\n", td + 2);
		for (int i = 0;i <= td;++i)
		{
			sort(cur[i].begin(), cur[i].end(), cmp);
			if (A.first < B.first) swap(A, B);
			while ((int)cur[i].size() > 0 && A.first > 0)
			{
				ans[cur[i].back() - 1] = A.second;
				A.first--; cur[i].pop_back();
			}
			while ((int)cur[i].size() > 0 && B.first > 0)
			{
				ans[cur[i].back() - 1] = B.second;
				B.first--; cur[i].pop_back();
			}
		}
		ans[n] = '\0';puts(ans);
	}
	return 0;
}