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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

struct UF {
	int n; vector<int> par, sz;
	void init(int _n) { n = _n; par = sz = vector<int>(n); REP(i, n) par[i] = i, sz[i] = 1; }
	int find(int x) { if (par[x] == x) return x; return find(par[x]); }
	void unite(int x, int y) { x = find(x), y = find(y); if (x == y) return; if (sz[x] < sz[y]) swap(x, y); par[y] = x, sz[x] += sz[y]; }
};

const int MAXN = 100000;

int n, na;
int par[MAXN];
char ans[MAXN + 1];

vector<int> ch[MAXN];
int dep[MAXN];
vector<int> bydep[MAXN];
UF uf;
vector<int> bysz[MAXN + 1];

bool can[MAXN + 1];
pair<int, int> act[MAXN + 1];
int szrem[MAXN + 1];
bool use[MAXN];

void dfsinit(int at) {
	dep[at] = par[at] == -1 ? 0 : dep[par[at]] + 1;
	for (int to : ch[at]) dfsinit(to);
}

int solve() {
	REP(i, n) if (par[i] != -1) ch[par[i]].PB(i);
	dfsinit(0);
	
	REP(i, n) bydep[dep[i]].PB(i);
	uf.init(n);
	for (int d = n - 1; d >= 0; --d) {
		int fst = -1;
		for (int at : bydep[d]) if (fst == -1) fst = at; else uf.unite(at, fst);
	}
	REP(at, n) if (uf.find(at) == at) bysz[uf.sz[at]].PB(at);
	//printf("bysz:"); FORE(sz, 1, n) if (SZ(bysz[sz]) != 0) printf(" %d*%d", SZ(bysz[sz]), sz); puts("");

	REPE(i, na) can[i] = false;
	can[0] = true; act[0] = MP(-1, -1);
	FORE(sz, 1, n) if (SZ(bysz[sz]) != 0) {
		int lim = SZ(bysz[sz]);
		REP(offset, sz) {
			int need = INT_MAX;
			for (int i = offset; i <= na; i += sz) {
				if (can[i]) { need = 0; continue; }
				if (need != INT_MAX) ++need;
				if (need <= lim) can[i] = true, act[i] = MP(need, sz);
			}
		}
	}

	int ndep = 0;
	REP(i, n) if (SZ(bydep[i]) != 0) ++ndep;

	if (can[na]) {
		//printf("YES\n");
		vector<pair<int, int>> how;
		for (int i = na; i != 0; i -= act[i].first * act[i].second) how.PB(act[i]);
		//printf("how:"); REPSZ(i, how) printf(" %d*%d", how[i].first, how[i].second); puts("");
		FORE(i, 1, n) szrem[i] = 0;
		REPSZ(i, how) szrem[how[i].second] += how[i].first;
		REP(i, n) use[i] = false;
		REP(at, n) {
			int leader = uf.find(at), sz = uf.sz[leader];
			if (!use[leader] && szrem[sz] > 0) use[leader] = true, --szrem[sz];
			ans[at] = use[leader] ? 'a' : 'b';
		}
		return ndep;
	} else {
		int lastskip = -1;
		int arem = na;
		REP(i, n) ans[i] = 'b';
		REP(d, n) {
			if (SZ(bydep[d]) <= arem) {
				for (int at : bydep[d]) ans[at] = 'a', --arem;
			} else {
				lastskip = d;
			}
		}
		if (lastskip != -1) for (int at : bydep[lastskip]) if (SZ(ch[at]) == 0 && arem > 0) ans[at] = 'a', --arem;
		assert(arem == 0);
		return ndep + 1;
	}
}

void run() {
	scanf("%d%d", &n, &na);
	par[0] = -1; FOR(i, 1, n) scanf("%d", &par[i]), --par[i];
	printf("%d\n", solve());
	printf("%s\n", ans);
}

int main() {
	run();
	return 0;
}