#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

#define mp make_pair
#define pb push_back
#define fi first
#define se second

template <typename T> void inline read(T &x) {
	x = 0; int f = 1; char s = getchar();
	while (s < '0' || s > '9') { if (s == '-') { f = -1;} s = getchar(); }
	while (s >= '0' && s <= '9') x = x * 10 + (s ^ 48), s = getchar();
	x *= f;
}

template <typename T> bool inline chkMin(T &x, T y) { return y < x ? x = y, 1 : 0; }
template <typename T> bool inline chkMax(T &x, T y) { return y > x ? x = y, 1 : 0; }

const int N = 77780, M = 77780, S = 15, K = 2 * N, INF = 1e9;

int n, m, len[N], c[M], tp[M], D[M], s, t, in[M], out[M], L[M], R[M];

map<string, int> ID;

char s1[S], s2[S], s3[S];

string inline get(char g[S]) {
	string s = "";
	for (int i = 1; g[i]; i++)
		s += g[i];
	return s;
} 


map<pair<int, int>, vector<int> > MI[2];

void inline apd(int x, int y) {
	R[x] = y, L[y] = x;
}

int q[K], d[K], cur[K], ac[N];

int head[K], numE = 1;

bool ban[M][2];

string O[M], A[M], B[M];

struct E{
	int next, v, w;
} e[M * 8];



set<int> bel[M][2];

int z[M], ar[N], tot;

bool vis[M];

void inline clr() {
	ID.clear();
	for (int i = 1; i <= n; i++) len[i] = 0, bel[i][0].clear(), bel[i][1].clear();
	for (int i = 1; i <= m; i++) L[i] = R[i] = vis[i] = 0, c[i] = tp[i] = ban[i][0] = ban[i][1] = d[i] = 0;
	for (int i = 1; i <= t; i++) head[i] = 0;
	for (int i = 2; i <= numE; i++) 
		e[i].next = e[i].v = e[i].w = 0;
	numE = 1;
	MI[0].clear();
	MI[1].clear();
}

void inline add(int u, int v, int w) {
	e[++numE] = (E) { head[u], v, w };
	head[u] = numE;
}

void inline addE(int u, int v, int w) {
	add(u, v, w), add(v, u, 0);
}

bool inline bfs() {
	for (int i = 1; i <= t; i++) d[i] = 0;
	int hh = 0, tt = 0;
	q[0] = s;
	d[s] = 1; cur[s] = head[s];
	while (hh <= tt) {
		int u = q[hh++]; 
		for (int i = head[u]; i; i = e[i].next) {
			int v = e[i].v;
			if (e[i].w && !d[v]) {
				d[v] = d[u] + 1;
				q[++tt] = v; cur[v] = head[v];
				if (v == t) return 1;
			}
		}
	}
	return 0;
}

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

int inline work() {
	int ans = 0, res = 0;
	int zg = 0;
	while (bfs())
		while (res = dinic(s, INF)) ans += res, zg++;
//	cerr << zg << "??\n";
	return ans;
}

int ret[M], ct;

void inline print() {
	tot = 0;
	for (int i = 1; i <= m; i++) {
		if (ban[i][1] && ban[i][0]) continue;
		string o = O[i], a = A[i], b = B[i];
		//cout << o << " " << a << " " << b << endl;
		if (!ban[i][1]) {
			if (o == "loushang" && ID.count(b)) {
				if (e[z[i]].w) {
					ar[++tot] = i;
					bel[c[i]][1].erase(i);
				}
			}
		}

		if (!ban[i][0]) {
			if (o == "louxia" && ID.count(b)) {
				if (e[z[i]].w) {
					ar[++tot] = i;
					bel[c[i]][0].erase(i);
				}
			}
		}	
	}
	for (int i = 1; i <= tot; i++) {
		int u = ar[i], op = tp[u], de = O[u] == "loushang" ? 0 : 1;
		assert(bel[op][de].size());
		int v = *bel[op][de].begin();
		bel[op][de].erase(v);
		if (O[u] == "loushang") {
			apd(u, v); 
		} else apd(v, u);
	}
	for (int i = 1; i <= m; i++) {
		if (!vis[i] && !L[i]) {
			int p = i;
			while (p) {
				vis[p] = 1;
				p = R[p];
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		if (!vis[i]) {
			int p = i;
			while (p && !vis[p]) {
				vis[p] = 1;
				p = R[p];
			}
			int A = i, B = R[i];
			if (O[A] == "loushang") {
				int Bt = ac[c[B]];
				int Tr = L[Bt];
				R[A] = Bt;
				L[Bt] = A;
				if (Tr) R[Tr] = B;
				L[B] = Tr;
			} else {
				int At = ac[c[A]];
				int Tr = R[At];
				R[At] = B, L[B] = At;
				R[A] = Tr;
				if (Tr) L[Tr] = A;
			}
		}
	}
	for (int i = 1; i <= m; i++) vis[i] = 0;
	tot = 0;
	for (int i = 1; i <= m; i++) {
		if (!vis[i] && !L[i]) {
			int p = i;
			while (p) {
				ret[++tot] = p;
				vis[p] = 1;
				p = R[p];
			}
		}
	}
	for (int i = 1; i <= m; i++) printf("%d ", ret[i]);
	puts("");
	int ma = 0;
	for (int i = 1; i < m; i++) {
		int u = ret[i], v = ret[i + 1];
		if (O[u] == "loushang" && tp[u] == c[v]) ma++;
		if (O[v] == "louxia" && tp[v] == c[u]) ma++;
	}
	assert(ma == ct);
}


int main() {
	int T; read(T);
	while (T--) {
		read(n), read(m);
		s = 2 * n + 1, t = 2 * n + 2;
		for (int i = 1; i <= n; i++) {
			in[i] = out[i] = 0;
			scanf("%s", s1 + 1);
			ac[i] = 0;
			len[i] = strlen(s1 + 1);
			string o = "";
			for (int j = 1; s1[j]; j++)
				o += s1[j];
			ID[o] = i;
		}
		ct = 0;
		for (int i = 1; i <= m; i++) {
			scanf("%s%s%s", s1 + 1, s2 + 1, s3 + 1);
			string o = get(s3), a = get(s1), b = get(s2);
			O[i] = o, A[i] = a, B[i] = b;
			c[i] = ID[a];
			if (o == "loushang" && ID.count(b)) {
				tp[i] = ID[b];
				PII F = mp(c[i], tp[i]);
				PII G = mp(tp[i], c[i]);
				D[i] = 1;
				if (MI[1][G].size()) {
					ban[MI[1][G].back()][0] = 1;
					ban[i][1] = 1;
					apd(i, MI[1][G].back());
					MI[1][G].pop_back();
					ct += 2;
				} else MI[0][F].pb(i);
			} else if (o == "louxia" && ID.count(b)) {
				tp[i] = ID[b];
				D[i] = 2;
				PII F = mp(c[i], tp[i]);
				PII G = mp(tp[i], c[i]);
				if (MI[0][G].size()) {
					ban[MI[0][G].back()][1] = 1;
					ban[i][0] = 1;
					apd(MI[0][G].back(), i);
					MI[0][G].pop_back();
					ct += 2;
				} else MI[1][F].pb(i);
			} else {
				ac[c[i]] = i;
			}
		}
//		cerr << n << " " << m << endl;
//		cerr << ct << endl;
		for (int i = 1; i <= m; i++) {
			if (ban[i][1] && ban[i][0]) continue;
			string o = O[i], a = A[i], b = B[i];
			//cout << o << " " << a << " " << b << endl;
			if (!ban[i][1]) {
				bel[c[i]][1].insert(i);
				if (o == "loushang" && ID.count(b)) {
					addE(tp[i] + n, c[i], 1);
					z[i] = numE;
				}
				in[c[i]]++;
				//addE(c[i], t, 1);
			}

			if (!ban[i][0]) {
				bel[c[i]][0].insert(i);
				if (o == "louxia" && ID.count(b)) {
					addE(c[i] + n, tp[i], 1);
					z[i] = numE;
				}
				out[c[i]]++;
				//addE(s, c[i] + n, 1);
			}	
		}
		for (int i = 1; i <= n; i++) {
			if (in[i]) addE(i, t, in[i]);
			if (out[i]) addE(s, i + n, out[i]);
		}
		ct += work();
		printf("%d\n", ct);
		print();
		clr();
	}
}