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>
#define ll long long
#define pb push_back
#define mkp make_pair
#define si set < int >
#define vi vector < int >
#define pii pair < int, int >
#define mii map < int, int >
#define p_q priority_queue
#define INF ((1 << 30) - 1)
#define FI(n) FastIO::read(n)
#define FO(n) FastIO::write(n)
#define ull unsigned long long
#define mst(a, b) memset(a,b,sizeof(a))
#define foR(i, k, j) for(int i = (k); i >= (j); i--)
#define For(i, k, j) for(int i = (k); i <= (j); i++)
#define Foe(i, u) for(int i = lst[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define Fin(s) freopen(s, "r", stdin)
#define Fout(s) freopen(s, "w", stdout)
#define file(s) Fin(s".in"), Fout(s".out")
//#define int long long
const int P = 998244353; //
using namespace std;
template <typename T> inline void ckmax(T &a, T b) {(a < b) && (a = b);}
template <typename T> inline void ckmin(T &a, T b) {(a > b) && (a = b);}
inline int mul(int a, int b) {return 1ll * a * b % P;}
inline int add(int a, int b) {return a + b >= P ? a + b - P : a + b;}
inline int sub(int a, int b) {return a - b >= 0 ? a - b : a - b + P;}
inline void mulmod(int &a, int b) {a = mul(a, b);}
inline void addmod(int &a, int b) {((a += b) >= P) && (a -= P);}
inline void submod(int &a, int b) {((a -= b) < 0) && (a += P);}
inline int ksm(int a, int b) {int ans=1; for(;b;b>>=1) {if(b&1) ans=1ll*ans*a%P;a=1ll*a*a%P;}return ans;}
inline int inv(int a) {return ksm(a, P-2);}
namespace FastIO {
    const int SIZE=1<<16; char buf[SIZE], obuf[SIZE], str[64]; int bi=SIZE, bn=SIZE, opt;
    int read(char *s) {
        while (bn) {for (;bi<bn&&buf[bi]<=' ';bi++);if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}
        int sn=0;while (bn) {for (;bi<bn&&buf[bi]>' ';bi++) s[sn++]=buf[bi];if (bi<bn) break; bn=fread(buf,1,SIZE,stdin),bi=0;}s[sn]=0;return sn;
    }
    bool read(int& x) {if(x)x=0;int bf=0,n=read(str); if(!n) return 0; int i=0; if (str[i]=='-') bf=1,i=1; for(x=0;i<n;i++) x=x*10+str[i]-'0'; if(bf) x=-x; return 1;}
    void write(int x) {
        if(!x) obuf[opt++] = '0'; else {if(x<0) obuf[opt++]='-',x=-x;int sn=0; while(x)str[sn++]=x%10+'0',x/=10;for (int i=sn-1;i>=0;i--) obuf[opt++]=str[i];}
        if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}
    }
    void write(char x) {obuf[opt++]=x;if (opt>=(SIZE>>1)){fwrite(obuf, 1, opt, stdout); opt=0;}}
    void Fflush() { if (opt) fwrite(obuf, 1, opt, stdout); opt=0;}
};
inline int read() {int x; FI(x); return x;}
const int MAXN = 1e5 + 5;
int n, m, dep[MAXN], mxdep, cnt[MAXN], scnt[MAXN], siz[MAXN];
vector < int > e[MAXN], d[MAXN];
void dfs(int u, int fa) {
	dep[u] = dep[fa] + 1; d[dep[u]].pb(u);
	ckmax(mxdep, dep[u]); siz[u] = 1;
	for(auto v : e[u]) dfs(v, u), siz[u] += siz[v];
}
vector < pii > t;
bool f[505][MAXN];
int lst[505][MAXN], G[MAXN], ans[MAXN];
void getans(int i, int j) {
//	cerr << "! " << i << ' ' << j << endl; 
	if(i == 0) return void();
	assert(f[i][j] == 1); ans[t[i].first] = lst[i][j];
	getans(i - 1, j - t[i].first * lst[i][j]);
}

char res[MAXN];
int p[MAXN];
bool cmp(int a, int b) {
	return scnt[a] < scnt[b];
}
bool cmp2(int a, int b) {
	return siz[a] < siz[b];
}
signed main()
{ 
	#ifndef ONLINE_JUDGE
        file("pro");
    #endif
    n = read(), m = read();
    For(i, 2, n) {
    	int f = read();
		e[f].pb(i);	
    }
    dfs(1, 0);
    For(i, 1, mxdep) cnt[scnt[i] = d[i].size()]++;	
    t.pb(mkp(-1, -1)); For(i, 1, n) if(cnt[i]) t.pb(mkp(i, cnt[i]));	
    f[0][0] = 1;
	For(i, 1, t.size() - 1) {
		memset(G, 127 / 2, sizeof(G));
		For(j, 0, n) {
			if(f[i - 1][j]) G[j] = 0;
			else if(j >= t[i].first) G[j] = G[j - t[i].first] + 1;
		}
		For(j, 0, n) {
			if(G[j] <= t[i].second) {
				f[i][j] = 1; lst[i][j] = G[j];
			}
		}
	}
//	for(auto it : t) {
//		fprintf(stderr, "? %d %d\n", it.first, it.second);	
//	}
//	For(i, 1, t.size() - 1) {
//		For(j, 0, n) cerr << f[i][j] << ' ';
//		cerr << endl; 	
//	}
	For(i, 1, n) res[i] = ' '; res[n + 1] = '\0';
	cerr << mxdep << endl; 
	if(f[t.size() - 1][m]) {
		printf("%d\n", mxdep);
//		if(mxdep == 46) printf("?");
		getans(t.size() - 1, m);
//		For(i, 1, 10) cerr << ans[i] << ' ';
//		cerr << endl; 
		For(i, 1, mxdep) {
			if(ans[scnt[i]]) {
				for(auto u : d[i])
					res[u] = 'a'; 
				ans[scnt[i]]--;
			} else {
				for(auto u : d[i])
					res[u] = 'b';	
			}
		}
	} else {
		printf("%d\n", mxdep + 1);
//		if(mxdep == 27) printf("?\n");
		For(i, 1, mxdep) p[i] = i;
		For(i, 1, n) sort(d[i].begin(), d[i].end(), cmp2);
//		sort(p + 1, p + 1 + mxdep, cmp);
		pair < int, char > a = mkp(m, 'a'), b = mkp(n - m, 'b');
		For(i, 1, mxdep) {
			if(a.first < b.first) swap(a, b);
			while(d[i].size() > 0 && a.first > 0) {
				res[d[i].back()] = a.second;
				d[i].pop_back();
				a.first--;
			}
			while(d[i].size() > 0 && b.first > 0) {
				res[d[i].back()] = b.second;
				d[i].pop_back();
				b.first--;
			}
		}
//		cerr << x << ' ' << y << endl;
//		assert(x + y == d[p[mxdep]].size());
//		sort(d[p[mxdep]].begin(), d[p[mxdep]].end(), cmp2);
//		for(int i = 0; i < x; i++) res[d[p[mxdep]][i]] = 'a';
//		for(int i = x; i < y + x; i++) res[d[p[mxdep]][i]] = 'b';
	}
	printf("%s\n", res + 1);
    return FastIO::Fflush(), 0;
}
/*
我愿意接受为了更好归来的离开和更有意义的离开，但爱你的人会留下来，一定会留下来。

*/