#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 8e5 + 5;

int n, m, t;
int in[kMaxN * 2], out[kMaxN * 2], res[kMaxN], cur[kMaxN * 2];
bool del[kMaxN];
std::tuple<int, int, int> e[kMaxN], _e[kMaxN];
std::vector<int> vec[kMaxN], stk;
std::map<std::string, int> mp;
std::vector<std::pair<int, int>> G[kMaxN * 2];

namespace Dinic {
struct Edge {
  int v, w, id, pre;
} e[kMaxN * 10];

int tot = 1, n, s, t;
int tail[kMaxN * 2], cur[kMaxN * 2], dep[kMaxN * 2];

void init(int _n, int _s, int _t) {
  for (int i = 1; i <= n; ++i) tail[i] = cur[i] = dep[i] = 0;
  for (int i = 1; i <= tot; ++i) e[i] = {0, 0, 0};
  tot = 1, n = _n, s = _s, t = _t;
}
void adde(int u, int v, int w, int id) { e[++tot] = {v, w, id, tail[u]}, tail[u] = tot; }
void add(int u, int v, int w, int id) { adde(u, v, w, id), adde(v, u, 0, id); }

bool bfs() {
  std::queue<int> q;
  for (int i = 1; i <= n; ++i)
    cur[i] = tail[i], dep[i] = 1e9;
  q.emplace(s), dep[s] = 0;
  for (; !q.empty();) {
    int u = q.front(); q.pop();
    for (int i = tail[u]; i; i = e[i].pre) {
      int v = e[i].v, w = e[i].w;
      if (w && dep[v] == 1e9) {
        dep[v] = dep[u] + 1, q.emplace(v);
      }
    }
  }
  return dep[t] != 1e9;
}
int dfs(int u, int lim) {
  if (u == t || !lim) return lim;
  int flow = 0;
  for (int &i = cur[u]; i; i = e[i].pre) {
    int v = e[i].v, w = e[i].w;
    if (w && dep[v] == dep[u] + 1) {
      int fl = dfs(v, std::min(lim, w));
      if (!fl) dep[v] = 1e9;
      lim -= fl, flow += fl;
      e[i].w -= fl, e[i ^ 1].w += fl;
      if (!lim) break;
    }
  }
  return flow;
}
int maxflow() {
  int ans = 0;
  for (; bfs(); ans += dfs(s, 1e9)) {}
  return ans;
}
std::vector<int> getdel() {
  std::vector<int> vec;
  int flow = maxflow();
  for (int i = 1; i <= ::n; ++i) {
    for (int id = tail[i]; id; id = e[id].pre) {
      int j = e[id].v;
      if (j >= ::n + 1 && j <= 2 * ::n && !e[id].w) {
        vec.emplace_back(e[id].id);
      }
    }
  }
  return vec;
}
} // namespace Dinic

void init() {
  t = 0, stk.clear(), mp.clear();
  for (int i = 1; i <= m; ++i) del[i] = 0, vec[i].clear();
  for (int i = 1; i <= 2 * n + 1; ++i) G[i].clear(), cur[i] = in[i] = out[i] = 0;
}

void prework() {
  static std::tuple<int, int, int> tmp[kMaxN];
  std::set<std::tuple<int, int, int, int>> st;
  int _m = 0;
  for (int i = 1; i <= m; ++i) {
    auto [op, u, v] = e[i];
    if (op == 0 || op == 1) {
      auto it = st.lower_bound({op ^ 1, v, u, 0});
      if (it != st.end() && std::get<0>(*it) == (op ^ 1) && std::get<1>(*it) == v && std::get<2>(*it) == u) {
        if (op == 0) {
          tmp[++_m] = {2, u, v};
          vec[_m] = {std::get<3>(*it), i};
        } else {
          tmp[++_m] = {2, v, u};
          vec[_m] = {i, std::get<3>(*it)};
        }
        st.erase(it);
      } else {
        st.emplace(op, u, v, i);
      }
    } else {
      tmp[++_m] = {op, u, u};
      vec[_m] = {i};
    }
  }
  for (auto [op, u, v, i] : st) {
    tmp[++_m] = {op, u, v};
    vec[_m] = {i};
  }
  m = _m;
  for (int i = 1; i <= m; ++i) e[i] = tmp[i];
}

void getdeg(bool o = 0) {
  if (!o) {
    for (int i = 1; i <= 2 * n; ++i) in[i] = out[i] = 0;
  }
  for (int i = 1; i <= m; ++i) {
    if (del[i]) continue;
    auto [op, u, v] = e[i];
    if (op == 0) {
      ++out[u], ++in[v];
      if (o) G[u].emplace_back(v, i);
    } else if (op == 1) {
      ++out[v + n], ++in[u + n];
      if (o) G[v + n].emplace_back(u + n, i);
    } else {
      ++out[u], ++in[v + n];
      if (o) G[u].emplace_back(v + n, i);
    }
  }
}

void dfs(int u) {
  for (int i = cur[u]; i < (int)G[u].size(); i = cur[u]) {
    auto [v, id] = G[u][i];
    cur[u] = i + 1;
    dfs(v);
    stk.emplace_back(id);
  }
}

int getcnt() {
  int cnt = 0;
  for (int i = 1; i <= t; ++i) {
    auto [op, u, v] = _e[res[i]];
    if (op == 0 && i < t && v == std::get<1>(_e[res[i + 1]]) || op == 1 && i > 1 && v == std::get<1>(_e[res[i - 1]]))
      ++cnt;
  }
  return cnt;
}

void dickdreamer() {
  std::cin >> n >> m;
  init();
  for (int i = 1; i <= n; ++i) {
    std::string s;
    std::cin >> s;
    mp[s] = i;
  }
  for (int i = 1; i <= m; ++i) {
    std::string s1, s2, s3;
    std::cin >> s1 >> s2 >> s3;
    if (s3 == "loushang" && mp.count(s2)) {
      e[i] = {0, mp[s1], mp[s2]};
    } else if (s3 == "louxia" && mp.count(s2)) {
      e[i] = {1, mp[s1], mp[s2]};
    } else {
      int id = mp[s1];
      e[i] = {2, id, id};
    }
    _e[i] = e[i];
  }
  for (int i = 1; i <= m; ++i) vec[i] = {i};
  prework();
  // for (int i = 1; i <= m; ++i) {
  //   for (auto x : vec[i]) std::cout << x << ' ';
  //   std::cout << '\n';
  // }
  // std::cout << '\n';
  int S = 2 * n + 1, T = 2 * n + 2;
  Dinic::init(2 * n + 2, S, T);
  getdeg();
  // for (int i = 1; i <= 2 * n; ++i) std::cerr << in[i] << ' ' << out[i] << '\n';
  for (int i = 1; i <= n; ++i)
    if (in[i] > out[i])
      Dinic::add(S, i, in[i] - out[i], 0);
  for (int i = n + 1; i <= 2 * n; ++i)
    if (out[i] > in[i])
      Dinic::add(i, T, out[i] - in[i], 0);
  for (int i = 1; i <= m; ++i) {
    auto [op, u, v] = e[i];
    // std::cout << op << ' ' << u << ' ' << v << '\n';
    if (op == 0) {
      Dinic::add(v, u + n, 1, i);
    } else if (op == 1) {
      Dinic::add(u, v + n, 1, i);
    }
  }
  auto dvec = Dinic::getdel();
  for (int i = 1; i <= 2 * n; ++i) in[i] = out[i] = 0;
  for (auto i : dvec) {
    auto [op, u, v] = e[i];
    G[u].emplace_back(u + n, i), ++out[u], ++in[u + n];
    del[i] = 1;
  }
  getdeg(1);
  for (int i = 1; i <= 2 * n; ++i) {
    // if (i <= n) assert(in[i] <= out[i]);
    // else assert(in[i] >= out[i]);
    if (in[i] <= out[i]) {
      for (; in[i] < out[i];)
        G[2 * n + 1].emplace_back(i, 0), ++out[2 * n + 1], ++in[i];
    } else {
      for (; out[i] < in[i];)
        G[i].emplace_back(2 * n + 1, 0), ++out[i], ++in[2 * n + 1];
    }
  }
  // for (int i = 1; i <= 2 * n + 1; ++i) assert(in[i] == out[i]);
  dfs(2 * n + 1);
  for (auto x : stk) {
    for (auto i : vec[x]) res[++t] = i;
  }
  std::reverse(res + 1, res + 1 + t);
  std::cout << getcnt() << '\n';
  for (int i = 1; i <= t; ++i) std::cout << res[i] << " \n"[i == t];
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}