#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2.4e5+5;
const int inf = 2e9;

int n,m,ans;
map<string,int> mp;

struct edge {
	int to,nxt,f;
} e[N*10];

struct node {
	ll fr,to,op,id;
	bool operator < (const node &x) const {
		return make_tuple(op,fr,to)<make_tuple(x.op,x.fr,x.to);
	}
} em[N];

int len=1,lnk[N<<2];

int enc(int x,int op){
	return 2*m+x*2+op-1;
}

void add_edge(int u,int v,int cap){
	e[++len]={v,lnk[u],cap};
	lnk[u]=len;
	e[++len]={u,lnk[v],0};
	lnk[v]=len;
}

// max flow

int lvl[N<<2]; 

bool bfs(int S,int T){
	memset(lvl,-1,sizeof lvl);
	queue<int> q;
	q.push(S);
	lvl[S]=0;
	while (!q.empty()){
		int x=q.front();
		q.pop();
		if (x==T){
			return 1;
		}
		for (int i=lnk[x]; i; i=e[i].nxt){
			int y=e[i].to;
			if (e[i].f>0 && lvl[y]==-1){
				lvl[y]=lvl[x]+1;
				q.push(y);
			}
		}
	}
	return 0;
}

int dfs(int x,int T,int f){
	if (x==T){
		return f;
	}
	for (int i=lnk[x]; i; i=e[i].nxt){
		int y=e[i].to;
		if (e[i].f>0 && lvl[y]==lvl[x]+1){
			int d=dfs(y,T,min(f,e[i].f));
			if (d>0){
				e[i].f-=d;
				e[i^1].f+=d;
				return d;
			}
		}
	}
	return 0;
}

int max_flow(int S,int T){
	int flow=0;
	while (true){
		if (!bfs(S,T)){
			return flow;
		}
		int f;
		while ((f=dfs(S,T,inf))){
			flow+=f;
		}
	}
}

int S,T,m2;

ll ec2(ll x,ll y){
	ll res=(x<<20ll)|y;
	return res;
}

void bdf(){
	m2=m;
	multiset<node> st;
	for (int i=1; i<=m; i++){
		st.insert(em[i]);
	}
	while (st.size()){
		auto it=*st.begin();
		st.erase(st.begin());
		if (it.op!=1){
			continue;
		}
		auto it2=st.find({it.to,it.fr,2,0});
		if (it2!=st.end()){
			em[it.id].op=-1;
			em[it2->id].op=-1;
			++++ans;
			em[++m]=node{it.fr,it.to,3,ec2(it.id,it2->id)};
			st.erase(it2);
		}
	}
	S=2*m+2*n+1;
	T=S+1;
	for (int i=1; i<=m; i++){
		if (em[i].op!=-1){
			int X=em[i].fr,Y=em[i].to;
			add_edge(S,i,1),add_edge(i+m,T,1);
			if (em[i].op!=3){
				add_edge(i,enc(X,0),1),add_edge(enc(X,1),i+m,1);
				if (em[i].op==1){
					add_edge(i,enc(Y,1),1);
				}
				if (em[i].op==2){
					add_edge(enc(Y,0),i+m,1);
				}
			}
			else{
				add_edge(enc(X,1),i+m,1),add_edge(i,enc(Y,0),1);
			}
		}
	}
}

void cons(){
	for (int i=1; i<=m2; i++){
		cout<<i<<" ";
	}
	cout<<"\n";
}

void init(){
	len=1;
	mp.clear();
	memset(lnk,0,sizeof lnk);
	ans=0;
}

void solve(){
	cin>>n>>m;
	for (int i=1; i<=n; i++){
		string s;
		cin>>s;
		mp[s]=i;
	}
	for (int i=1; i<=m; i++){
		string s1,s2,s3;
		cin>>s1>>s2>>s3;
		int fr=mp[s1];
		int to=0,op=0;
		if (s3=="louxia" && mp.count(s2)){
			op=1;
			to=mp[s2];
		}
		else if (s3=="loushang" && mp.count(s2)){
			op=2;
			to=mp[s2];
		}
		em[i]=node{fr,to,op,i};
	}
	bdf();
	ans+=max_flow(S,T);
	cout<<ans<<"\n";
	cons();
	init();
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	freopen("community.in","r",stdin);
	freopen("community.out","w",stdout);
	int tc;
	cin>>tc;
	while (tc--){
		solve();
	}
	return 0;
}

是这样的，我写了一个我以为可以 $50$ 分的程序，但是它 T 了，为什么呢？按道理来说不是 $\mathcal{O}(m\sqrt{m})$ 的吗？