#include <bits/stdc++.h>
#define N 100011
#define pii pair<int,int>
#define s1 first
#define s2 second
using namespace std;
int n,m,T;
struct msg{int a,b,typ,id;}a[N];
map<string,int> mp;
int pvt[N];
int nxt[N],prv[N];
multiset<msg> st;
inline bool operator<(msg a,msg b)
{
	if(a.a!=b.a)return a.a<b.a;
	if(a.b!=b.b)return a.b<b.b;
	return a.typ<b.typ;
}
struct edge{int v,w,next;edge(){}edge(int _v,int _w,int _next){v=_v;w=_w;next=_next;}}e[N*20];int head[N*5],sz;
void insert(int u,int v,int w,int w2=0){e[++sz]=edge(v,w,head[u]);head[u]=sz;e[++sz]=edge(u,w2,head[v]);head[v]=sz;}
int s,t,dis[N*5],cur[N*5];
bool bfs()
{
	for(int i=s;i<=t;++i)dis[i]=-1;
	static queue<int> q;
	while(!q.empty())q.pop();
	q.push(s);dis[s]=0;
	while(!q.empty())
	{
		int p=q.front();q.pop();if(p==t)break;
		for(int i=head[p];~i;i=e[i].next)if(e[i].w&&!~dis[e[i].v])dis[e[i].v]=dis[p]+1,q.push(e[i].v);
	}
	return ~dis[t];
}
int dfs(int u,int fl)
{//printf("dfs(u:%d,fl:%d)\n",u,fl);
	if(u==t||!fl)return fl;
	int ans=0;
	for(int i=cur[u];~i;i=e[i].next)
	{
		cur[u]=i;
		if(e[i].w&&dis[e[i].v]==dis[u]+1)
		{
			int res=dfs(e[i].v,min(e[i].w,fl));
			fl-=res;ans+=res;e[i].w-=res;e[i^1].w+=res;if(!fl)break;
		}
	}
	return ans;
}
int dinic(){int ans=0;while(bfs()){for(int i=s;i<=t;++i)cur[i]=head[i];ans+=dfs(s,1e9);}return ans;}
mt19937 rnd(801);
int to[N],in[N];
void dfsW(int u,int c1,int c2)
{//printf("dfsW(u:%d,c1:%d,c2:%d)\n",u,c1,c2);
	if(u==t){to[c1]=c2-m;++in[c2-m];return;}
	for(int &i=cur[u];~i;i=e[i].next)if(!(i&1)&&!e[i].w)
	{
		if(1<=u&&u<=m)c1=u;
		if(m+1<=u&&u<=m+m)c2=u;
		dfsW(e[i].v,c1,c2);
		e[i].w=1;e[i^1].w=0;
		return;
	}
}
int L[N],R[N];
int getL(int a){return L[a]==a?a:L[a]=getL(L[a]);}
int getR(int a){return R[a]==a?a:R[a]=getR(R[a]);}
void link(int x,int y)
{//printf("link(%d->%d)\n",x,y);
	nxt[getR(x)]=getL(y);prv[getL(y)]=getR(x);
	L[getL(y)]=getL(x);R[getR(x)]=getR(y);
}
int main()
{
	scanf("%d",&T);while(T--)
	{
		scanf("%d%d",&n,&m);mp.clear();
		for(int i=1;i<=n;++i)
		{
			static char ss[111];
			scanf("%s",ss+1);
			mp[ss+1]=i;
		}
		for(int i=1;i<=m;++i)
		{
			static char s1[111],s2[111],s3[111];
			scanf("%s%s%s",s1,s2,s3);
			auto it=mp.find(s2);int id1=mp[s1];
			if(it!=mp.end()&&string(s3)=="louxia")a[i]=msg({id1,it->s2,0,i});
			else if(it!=mp.end()&&string(s3)=="loushang")a[i]=msg({id1,it->s2,1,i});
			else a[i]=msg({id1,0,2,i}),pvt[id1]=i;
		}
		// for(int i=1;i<=m;++i)printf("{a:%d,b:%d,typ:%d,id:%d}\n",a[i].a,a[i].b,a[i].typ,a[i].id);
		for(int i=1;i<=m;++i)nxt[i]=prv[i]=-1;
		st.clear();
		int ans=0;
		for(int i=1;i<=m;++i)L[i]=R[i]=i;
		for(int i=1;i<=m;++i)if(a[i].typ!=2)
		{
			auto it=st.find({a[i].b,a[i].a,a[i].typ^1,0});
			if(it!=st.end())
			{
				msg x=*it;
				st.erase(it);
				if(x.typ==0)link(i,x.id);
				else link(x.id,i);
				// printf("pair %d and %d\n",x.id,i);
				ans+=2;
			}
			else st.insert(a[i]);
		}
		s=0;t=2*m+n+n+1;
		for(int i=s;i<=t;++i)head[i]=-1;sz=-1;
		for(int i=1;i<=m;++i)
		{
			insert(s,i,1);insert(i+m,t,1);
			if(!~nxt[i]&&a[i].typ==1)insert(i,m+m+a[i].b,1);
			if(!~prv[i])insert(m+m+a[i].a,i+m,1);
			if(!~nxt[i])insert(i,m+m+n+a[i].a,1);
			if(!~prv[i]&&a[i].typ==0)insert(m+m+n+a[i].b,i+m,1);
		}
		int tt=dinic();
		printf("%d\n",tt+ans);
		for(int i=s;i<=t;++i)cur[i]=head[i];
		for(int i=1;i<=m;++i)to[i]=-1,in[i]=0;
		for(int _=1;_<=tt;++_)dfsW(s,0,0);
		// printf("to:");for(int i=1;i<=m;++i)printf("%d ",to[i]);putchar(10);
		// printf("in:");for(int i=1;i<=m;++i)printf("%d ",in[i]);putchar(10);
		static vector<vector<int>> pth;
		pth.clear();
		for(int i=1;i<=m;++i)if(!in[i])
		{
			int x=i;
			pth.push_back({});
			while(~to[x])
			{
				pth.back().push_back(x);
				int y=to[x];//link(x,y);
				to[x]=-1;--in[y];x=y;
			}
			pth.back().push_back(x);
		}
		// printf("prv:");for(int i=1;i<=m;++i)printf("%d ",prv[i]);putchar(10);
		// printf("nxt:");for(int i=1;i<=m;++i)printf("%d ",nxt[i]);putchar(10);
		for(int i=1;i<=m;++i)if(in[i])
		{
			static vector<int> cyc;
			int x=i;
			cyc.clear();
			while(~to[x])
			{
				cyc.push_back(x);
				int y=to[x];to[x]=-1;--in[y];x=y;
			}
			if(a[cyc[0]].typ==1)
			{
				for(int i=0;i+1<cyc.size();++i)link(cyc[i],cyc[i+1]);
				link(cyc.back(),pvt[a[cyc[0]].a]);
			}
			else
			{
				for(int i=0;i+1<cyc.size();++i)link(cyc[i],cyc[i+1]);
				link(pvt[a[cyc.back()].a],cyc[0]);
			}
		}
		for(auto &V:pth)
		{
			// printf("pth:");for(int x:V)printf("%d ",x);putchar(10);
			for(int i=0;i+1<V.size();++i)link(V[i],V[i+1]);
		}
		// printf("prv:");for(int i=1;i<=m;++i)printf("%d ",prv[i]);putchar(10);
		// printf("nxt:");for(int i=1;i<=m;++i)printf("%d ",nxt[i]);putchar(10);
		static vector<int> vres;
		vres.clear();
		for(int i=1;i<=m;++i)if(!~prv[i])
		{
			int x=i;
			while(~x)vres.push_back(x),x=nxt[x];
		}
		for(int x:vres)printf("%d ",x);
		putchar(10);
		assert(vres.size()==m);
		int cc=0;
		for(int i=0;i<vres.size();++i)
		{
			int u=vres[i];
			if(a[u].typ==1)
			{
				if(i+1<vres.size()&&a[vres[i+1]].a==a[u].b)++cc;
			}
			else if(a[u].typ==0)
			{
				if(i&&a[vres[i-1]].a==a[u].b)++cc;
			}
			// printf("i:%d cc:%d\n",i,cc);
		}
		assert(cc==tt+ans);
		sort(vres.begin(),vres.end());
		for(int i=1;i<vres.size();++i)assert(vres[i]!=vres[i-1]);
	}
	fclose(stdin);fclose(stdout);return 0;
}