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 PYTHON):

Solution:
from sys import stdin, stdout

n, a = map(int, stdin.readline().split())
p = [-1] + [int(x) - 1 for x in stdin.readline().split()]
g = [[] for i in range(n)]
for i in range(1, n):
	g[p[i]].append(i)

d = [-1 for i in range(n)]
d_all = [[] for i in range(n)]
d_lv = [[] for i in range(n)]
d_nlv = [[] for i in range(n)]

q = []
q.append(0)
d[0] = 0
while len(q) > 0:
	v = q.pop()
	d_all[d[v]].append(v)
	if len(g[v]) == 0:
		d_lv[d[v]].append(v)
	else:
		d_nlv[d[v]].append(v)
	for u in g[v]:
		if d[u] == -1:
			d[u] = d[v] + 1
			q.append(u)
mx = max(d) + 1
mx_lv_pos = -1
for i in range(mx):
	if mx_lv_pos == -1 or len(d_lv[i]) > len(d_lv[mx_lv_pos]):
		mx_lv_pos = i
wg = [len(d_all[i]) if i != mx_lv_pos else 0 for i in range(mx)]

un = sorted(list(set(wg)))[1:]
pos = {}
for i in range(len(un)):
	pos[un[i]] = i
vals = [[] for i in range(len(un))]
for i in range(len(wg)):
	if wg[i] != 0:
		vals[pos[wg[i]]].append(i)

lst = [[-1, -1] for i in range(n + 1)]
dp = [[False for j in range(n + 1)] for i in range(2)]
dp[0][0] = True

l = len(un)
for ii in range(l):
	i = ii & 1
	ni = i ^ 1
	dp[ni] = [False for j in range(n + 1)]
	lst_tk = [-1 for j in range(un[ii])]
	for j in range(n + 1):
		rm = j % un[ii]
		if dp[i][j]:
			lst_tk[rm] = j
			dp[ni][j] = True
		elif lst_tk[rm] >= 0 and (j - lst_tk[rm]) // un[ii] <= len(vals[ii]):
			dp[ni][j] = True
			lst[j] = [lst_tk[rm], ii]
dp = dp[l & 1]
ans = mx
res = -1
if dp[a]:
	res = a
elif a - len(d_all[mx_lv_pos]) >= 0 and dp[a - len(d_all[mx_lv_pos])]:
	res = a - len(d_all[mx_lv_pos])
else:
	for i in range(a + 1):
		if dp[i] and ((len(d_nlv[mx_lv_pos]) <= a - i <= len(d_all[mx_lv_pos])) or (0 <= a - i <= len(d_lv[mx_lv_pos]))):
			res = i
			break
	ans += 1
cur = res
fin = set()
while cur > 0:
	p = lst[cur][0]
	x = lst[cur][1]
	while cur > p:
		fin.add(vals[x].pop())
		cur -= un[x]
s = [1 for i in range(n)]
a -= res

for i in range(mx + 1):
	if i in fin:
		for v in d_all[i]:
			s[v] = 0
	if i == mx_lv_pos:
		if a == len(d_all[i]):
			for v in d_all[i]:
				s[v] = 0
			a -= len(d_nlv[i])
		elif a != 0 and len(d_nlv[i]) <= a <= len(d_all[i]):
			a -= len(d_nlv[i])
			for v in d_nlv[i]:
				s[v] = 0
		for _ in range(a):
			s[d_lv[i].pop()] = 0
stdout.write(str(ans) + "\n")
stdout.write("".join(["ab"[x] for x in s]) + "\n")