//code by Emissary
#include<bits/stdc++.h>

#define vc vector
#define db double
#define fi first
#define se second
#define ll long long
#define mk make_pair
#define pb push_back
#define RI register int
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define OccDreamer
//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(int x){write(x), putchar(32);}
	inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;

const int MAXN = 1e6+5;

int n, m, len[MAXN], which[MAXN], maxlen;
int lc[MAXN], rc[MAXN], inl[MAXN], inr[MAXN];

char ans[MAXN], cur[MAXN], to[MAXN], tmp[MAXN];

//which=1, 全相同，which=2 XY 交替，which=3 正常节点 

bool vis[MAXN];

pair<int,int> type[MAXN][2][2]; 
// [i] 节点 i [0/1] S 和 rev S  [0/1] L,R 在哪边 

char str[MAXN], st[MAXN][2][2], A[MAXN], B[MAXN];

vc<int> F[MAXN], G[MAXN];

inline void dfs(int x, int L){
	vis[x]=1; len[x]=L; maxlen=max(maxlen,L);
	for(auto i:G[x]){
		if(!vis[i]) dfs(i,L+1);	
	}
	return ;
}	

inline void get(int x){
	//cerr << "GET:" << x << endl;
	if(which[x]==1){
		type[x][0][0]=type[x][0][1]=type[x][1][0]=type[x][1][1]=mk(0,0); //inl
		st[x][0][0]=st[x][0][1]=st[x][1][0]=st[x][1][1]=str[x]=str[inl[x]];
	}
	if(which[x]==2){
		if(len[x]==2){
			type[x][0][0]=mk(0,0), type[x][0][1]=mk(1,0);
			type[x][1][0]=mk(1,0), type[x][1][1]=mk(0,0);
			st[x][0][0]=st[x][1][1]=str[inr[x]]; 
			st[x][0][1]=st[x][1][0]=str[inl[x]];
			A[x]=str[inl[x]], B[x]=str[inr[x]];
		}
		else{
			A[x]=A[inl[x]], B[x]=B[inl[x]];
			//cerr << "x=" << x << ' ' << A[x] << ' ' << B[x] << endl;
			int o;
			if(A[inr[x]]==A[x]) o=1;
			else o=0;
			type[x][0][0]=mk(0,0), type[x][0][1]=mk(1,o);
			type[x][1][0]=mk(0,1), type[x][1][1]=mk(1,o^1);
			if(len[x]&1){
				st[x][0][0]=A[x]; st[x][0][1]=A[x];
				st[x][1][0]=B[x]; st[x][1][1]=B[x];
			}	
			else{
				st[x][0][0]=B[x]; st[x][0][1]=A[x];
				st[x][1][0]=A[x]; st[x][1][1]=B[x];	
			}
		}
	}
	if(which[x]==3){
		if(which[inl[x]]!=2 && which[inr[x]]!=2){
			int com;
			int a=inl[x], b=inr[x];
			if(inl[a]==inl[b] || inl[a]==inr[b]) com=inl[a];
			else com=inr[a]; char c='.', d='.'; int posc, posd;
			for(int j=0;j<2;++j){
				if(type[a][0][j].fi==(com==inr[a])){
					if(j==0) c=st[a][0][j], posd=j;
					else c=st[a][0][j], posc=j;
				}
				if(type[b][0][j].fi==(com==inr[b])){
					if(j==0) d=st[b][0][j], posd=j;
					else d=st[b][0][j], posd=j;
				}
			}
			//cerr << "pos:" << posc << ' ' << posd << endl;
			if(posc!=posd){
				if(posc==0) type[x][0][1]=mk(0,0), type[x][0][0]=mk(1,0);
				else type[x][0][1]=mk(1,0), type[x][0][0]=mk(0,0);
			}
			else{
				int ox=0, oy=0; oy^=1; posd^=1; d=st[b][1][posd];
				if(posc==0) type[x][0][1]=mk(0,ox), type[x][0][0]=mk(1,oy);
				else type[x][0][1]=mk(1,oy), type[x][0][0]=mk(0,ox);
			}
			st[x][0][0]=d; st[x][0][1]=c;
			//cerr << "c=" << c << ' ' << "d=" << d << endl;
			type[x][1][1]=type[x][0][0];
			type[x][1][1].se^=1;
			type[x][1][0]=type[x][0][1];
			type[x][1][0].se^=1;
			st[x][1][1]=st[x][0][0];
			st[x][1][0]=st[x][0][1];
		}	
		else{
			if(which[inl[x]]==2) swap(inl[x],inr[x]);
			int a=inl[x], b=inr[x];
			int com=-1;
			if(inl[a]==inl[b] || inl[a]==inr[b]) com=inl[a];
			else if(inr[a]==inl[b] || inr[a]==inr[b]) com=inr[a]; 
			if((inl[a]==inl[b] || inl[a]==inr[b]) && (inr[a]==inl[b] || inr[a]==inr[b])){
				A[x]=A[a]; B[x]=B[a];
				type[x][0][0]=mk(0,0);
				st[x][0][0]=A[x]; int o=0;
				if(A[b]==B[x]) o=0;
				else o=1;
				type[x][0][1]=mk(1,o);
				st[x][0][1]=A[x];
				type[x][1][1]=type[x][0][0];
				type[x][1][0]=type[x][0][1];
				st[x][1][1]=B[x];
				st[x][1][0]=B[x];
				return ;	
			}
			int u=A[b], v=B[b]; bool flag=0;
			for(int i=0;i<2 && !flag;++i){
				for(int j=0;j<2 && !flag;++j){
					//cerr << a << ' ' << i << ' ' << j << ' ' << type[a][i][j].fi << ' ' << type[a][i][j].se << endl;
					if(type[a][i][j].se==0 && type[a][i][j].fi==(com==inr[a])){
						if(j==0){
							type[x][0][1]=mk(0,i);
							int w=st[a][i][j^1];
							st[x][0][1]=u+v-w;
							st[x][0][0]=st[a][i][j];
							int o;
							if(u+v-w==u) o=0;
							else o=1; 
							type[x][0][0]=mk(1,o);
							flag=1;
						}	
						else{
							type[x][0][0]=mk(0,i);
							int w=st[a][i][j^1];
							st[x][0][1]=st[a][i][j];
							st[x][0][0]=u+v-w;
							int o;
							if(u+v-w==u) o=0;
							else o=1;
							type[x][0][1]=mk(1,o^1);
							flag=1;
						}
					}
				}
			}
			if(len[x]&1){
				type[x][1][1]=type[x][0][0];
				type[x][1][1].se^=1;
				type[x][1][0]=type[x][0][1];
				type[x][1][0].se^=1;
				st[x][1][1]=st[x][0][0];
				st[x][1][0]=st[x][0][1];
			}
			else{
				type[x][1][1]=type[x][0][0];
				if(type[x][1][1].fi!=1) type[x][1][1].se^=1;
				type[x][1][0]=type[x][0][1];
				if(type[x][1][0].fi!=1) type[x][1][0].se^=1;
				st[x][1][1]=st[x][0][0];
				st[x][1][0]=st[x][0][1];		
			}
		}
		
	}
	/*
	cerr << "info:" << x << ' ' << str[x] << ' ' << A[x] << ' ' << B[x] << endl;
	cerr << "0:" << inl[x] << ' ' << inr[x] << endl;
	for(int i=0;i<2;++i){
		if(i==0) cerr << "L:" << endl;
		else cerr << "R:" << endl;
		if(type[x][0][i].fi==0) cerr << inl[x] << ' ';
		else cout << inr[x] << ' ';	
		if(type[x][0][i].se==0) cerr << "S:" << ' ' << st[x][0][i] << endl;
		else cerr << "F(S):" << ' ' << st[x][0][i] << endl;
	}
	cerr << "inforev:" << x << ' ' << str[x] << ' ' << B[x] << ' ' << A[x] << endl;
	cerr << "0:" << inl[x] << ' ' << inr[x] << endl;
	for(int i=0;i<2;++i){
		if(i==0) cerr << "L:" << endl;
		else cerr << "R:" << endl;
		if(type[x][1][i].fi==0) cerr << inl[x] << ' ';
		else cout << inr[x] << ' ';	
		if(type[x][1][i].se==0) cerr << "S:" << ' ' << st[x][1][i] << endl;
		else cerr << "F(S):" << ' ' << st[x][1][i] << endl;
 }*/
	return ;
}

bool mark[124];

inline void chkmin(){
	char now='a';
	memset(mark,0,sizeof mark);
	for(int i=1;i<=maxlen;++i){
		if(mark[cur[i]]) tmp[i]=to[cur[i]];
		else mark[cur[i]]=1, to[cur[i]]=now, now++, tmp[i]=to[cur[i]];	
	}
	for(int i=1;i<=maxlen;++i){
		if(ans[i]<tmp[i]) return ;		
		if(ans[i]>tmp[i]) break;
	}
	for(int i=1;i<=maxlen;++i) ans[i]=tmp[i];
	return ;
}

inline void calc(int x){
	int now=x, w=0;
	while(len[now]>1){
		cur[len[now]]=st[now][w][0];
		int X=type[now][w][0].fi, Y=type[now][w][0].se;
		now=X?inr[now]:inl[now], w=Y;
	}
	cur[1]=str[now]; chkmin();
	if(which[x]==3) reverse(cur+1,cur+1+len[x]); 
	else for(int i=1;i<=now;++i) cur[i]=(i%2==1?B[x]:A[1]);
	chkmin();
}

inline void solve(){
	n=read(), m=read(); int p[20];
	for(int i=1;i<=n;++i) p[i]=i; //srand(7);
//	random_shuffle(p+1,p+1+n);
//	for(int i=1;i<=n;++i) cout << p[i] << ' '; cout << endl;
	for(int i=1;i<=n;++i) ans[i]='z', G[i].clear(); maxlen=0;
	for(int i=1;i<=n;++i) inl[i]=inr[i]=vis[i]=0, which[i]=3;
	for(int i=1;i<=m;++i){
		int x, y;
		x=read(), y=read();
	//	x=p[x], y=p[y];
		if(inl[y]) inr[y]=x;
		else inl[y]=x;
		G[x].pb(y);
	}
	for(int i=1;i<=n;++i) vis[i]=0;
	char now='a';
	for(int i=1;i<=n;++i)
		if(inl[i]==0) dfs(i,1), str[i]=now, now++;
	for(int i=1;i<=n;++i) if(inl[i]<inr[i]) swap(inl[i],inr[i]);
	for(int i=1;i<=n;++i){
		if(inl[i] && inl[i] && len[i]!=1){
			int o=inl[inl[i]], p=inr[inl[i]];
			if(inl[inr[i]]==o && inr[inr[i]]==p && o && p) which[i]=which[inl[i]]=which[inr[i]]=which[o]=which[p]=2;
		}
		if(len[i]==2 && inl[i] && inr[i]) which[i]=2;
	}
	for(int i=1;i<=n;++i) F[i].clear();
	for(int i=1;i<=n;++i){
		if(len[i]==1 || !inr[i]) which[i]=1;
		F[len[i]].pb(i);	
	}
	int las=1;
	for(int i=2;i<=n;++i){
		for(auto j:F[i]){
			get(j);
			las=j;
		}
	}
	calc(las);
	for(int i=1;i<=maxlen;++i) putchar(ans[i]); putchar(10); 
}

signed main(){
	int t=read();
	while(t--) solve();
	return 0;
}
/*
1
11 16
1 3
1 4
1 5
2 4
2 5
3 6
3 7
4 7
4 8
5 8
6 9
7 9
7 10
8 10
9 11
10 11
aaaba
*/