#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int N = 2.5e5 + 5;
const int maxn = 327800;
const int maxm = 2.5e5 + 5;
const int inf = 2e9 + 7;

bool vis[N], ins[N];
int U[N], V[N], pos[N];
int pre[N], nxt[N], id[N], id2[N], typ[N], bpos[N], epos[N];
vector<int> bg[77800], ed[77800], lx, ls;
unordered_map<string, int> mp;
set<pair<pii, int> > st;

struct edge
{
	int v, next;
	int flow;
}e[3000005];
int head[maxn], tot;

inline void addedge(int u, int v, int c)
{
	e[++tot] = (edge){v, head[u], c}; head[u] = tot;
	e[++tot] = (edge){u, head[v], 0}; head[v] = tot;
}

int n, m, S, T;
int d[maxn], cur[maxn];

bool bfs()
{
	queue<int> q;
	for (int i = S; i <= T; i++) d[i] = 0, cur[i] = head[i];
	d[S] = 1; q.push(S);
	while (!q.empty())
	{
		int u = q.front(); q.pop();
		for (int i = head[u]; ~i; i = e[i].next)
		{
			int v = e[i].v;
			if (!d[v] && e[i].flow)
			{
				d[v] = d[u] + 1;
				if (v == T) return true;
				q.push(v);
			}
		}
	}
	return false;
}

int dfs(int u, int flow)
{
	if (u == T || !flow) return flow;
	int rest = flow;
	for (int i = cur[u]; ~i; i = e[i].next)
	{
		int v = e[i].v;
		if (d[v] == d[u] + 1 && e[i].flow)
		{
			int k = dfs(v, min(rest, e[i].flow));
			if (!k) d[v] = 0;
			e[i].flow -= k;
			e[i ^ 1].flow += k;
			rest -= k;
			if (!rest) return flow;
		}
		cur[u] = i;
	}
	return flow - rest;
}

int Dinic()
{
	int maxflow = 0;
	while (bfs()) maxflow += dfs(S, inf);
	return maxflow;
}

int main()
{	
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int TT;
	cin >> TT;
	while (TT--)
	{
		cin >> n >> m;
		mp.clear(); st.clear();
		lx.clear(); ls.clear();
		for (int i = 1; i <= n; i++)
		{
			bg[i].clear(); ed[i].clear();
			string str;
			cin >> str;
			mp[str] = i;
		}
		mp["loushang"] = n + 1;
		mp["louxia"] = n + 2;
		
		for (int i = 1; i <= m; i++)
		{
			pre[i] = nxt[i] = ins[i] = typ[i] = 0;
			string st1, st2, st3;
			cin >> st1 >> st2 >> st3;
			int u = mp[st1], x = mp[st2], y = mp[st3];
			if (x >= 1 && x <= n && y > n)
			{
				U[i] = u, V[i] = x;
				if (y == n + 1) typ[i] = 2;
				else typ[i] = 1;
			}
			else
			{
				U[i] = V[i] = u;
				pos[u] = i;
				bg[u].emplace_back(i);
				ed[u].emplace_back(i);
			}
		}
		
		int ans = 0;
		for (int x = 1; x <= m; x++)	
			if (typ[x] == 2) st.insert(make_pair(make_pair(U[x], V[x]), x));
		for (int x = 1; x <= m; x++)
		{
			if (typ[x] != 1) continue;
			pii tmp = make_pair(V[x], U[x]);
			auto it = st.lower_bound(make_pair(tmp, 0));
			if (it == st.end()) continue;
			if ((*it).first == tmp)
			{
				int y = (*it).second;
				nxt[y] = x;
				pre[x] = y;
				ans += 2;
				ins[x] = ins[y] = 1;
				bg[U[x]].emplace_back(x);
				ed[V[x]].emplace_back(y);
				st.erase(it);
			}
		}
		for (int x = 1; x <= m; x++)
		{
			if (ins[x]) continue;
			if (typ[x] == 2) lx.emplace_back(x), ed[U[x]].emplace_back(x);
			else if (typ[x] == 1) ls.emplace_back(x), bg[U[x]].emplace_back(x);
		}
		
		int n1 = lx.size(), n2 = ls.size();
		S = 0, T = n1 + n2 + (n << 1) + 1;
		for (int i = S; i <= T; i++) head[i] = -1; tot = -1;
		
		for (int i = 1; i <= n1; i++)
		{
			addedge(S, i, 1);
			id2[i] = tot - 1;
			addedge(i, n1 + n2 + n + V[lx[i - 1]], 1);
			id[i] = tot - 1;
		}
		for (int i = 1; i <= n2; i++)
		{
			addedge(n1 + n2 + V[ls[i - 1]], i + n1, 1);
			id[i + n1] = tot - 1;
			addedge(i + n1, T, 1);
			id2[i + n1] = tot - 1;
		}
		for (int i = 1; i <= n; i++)
		{
			addedge(S, i + n1 + n2, bg[i].size());
			addedge(i + n + n1 + n2, T, ed[i].size());
		}
		
		ans += Dinic();
		for (int i = 1; i <= n1; i++)
			addedge(i, n1 + n2 + U[lx[i - 1]], 1);
		for (int i = 1; i <= n2; i++)
			addedge(n1 + n2 + n + U[ls[i - 1]], i + n1, 1);
		
		cout << ans + Dinic() << "\n";
		
		for (int j = 1; j <= n; j++)
		{
			int u = n1 + n2 + j;
			for (int i = head[u]; ~i; i = e[i].next)
			{
				int v = e[i].v;
				if (v && v <= n1 && e[i].flow) bg[j].emplace_back(lx[v - 1]);
			}
			
			u = n1 + n2 + n + j;
			for (int i = head[u]; ~i; i = e[i].next)
			{
				int v = e[i].v;
				if (v > n1 && v <= n1 + n2 && !e[i].flow)
					ed[j].emplace_back(ls[v - n1 - 1]);
			}
		}
		for (int i = 1; i <= n; i++)
		{
			bpos[i] = bg[i].size() - 1;
			epos[i] = ed[i].size() - 1;
		}
		
		for (int i = 1; i <= n1 + n2; i++)
		{
			if (e[id2[i]].flow) continue;
			if (e[id2[i]].v == T)
			{
				if (e[id[i]].flow) continue;
				int p = ls[i - n1 - 1];
				int x = bg[V[p]][bpos[V[p]]]; bpos[V[p]]--;
				nxt[x] = p; pre[p] = x;
			}
			else
			{
				if (e[id[i]].flow) continue;
				int p = lx[i - 1];
				int x = ed[V[p]][epos[V[p]]]; epos[V[p]]--;
				nxt[p] = x; pre[x] = p;
			}
		}
		
		for (int i = 1; i <= m; i++) vis[i] = 0;
		for (int i = 1; i <= m; i++)
			if (!pre[i] && !vis[i])
				for (int j = i; j; j = nxt[j]) vis[j] = 1;
		for (int i = 1; i <= m; i++)
			if (!vis[i])
			{
				int x = U[i], y = pre[i], z = pre[pos[x]];
				vis[i] = 1;
				for (int j = nxt[i]; j != i; j = nxt[j]) vis[j] = 1;
				if (typ[y] == 2)
				{
					nxt[z] = i; pre[i] = z;
					pre[pos[x]] = y; nxt[y] = pos[x];
				}
				else
				{
					y = nxt[i], z = nxt[pos[x]];
					pre[z] = i; nxt[i] = z;
					nxt[pos[x]] = y; pre[y] = pos[x];
				}
			}
		
		for (int i = 1; i <= m; i++)
			if (!pre[i])
				for (int j = i; j; j = nxt[j]) cout << j << " ";
		cout << "\n";
	}
	return 0;
}