#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <cassert>

using namespace std;

typedef vector<int> VI;

#define PB push_back
#define REP(i,n) for(int i=0; i<(n); ++i)

#define ASF assert(false);

struct BipartiteDisjointSet {
  VI parent, rank, enemy, size;
  //parent : [1,n)
  BipartiteDisjointSet(int n) : parent(n), rank(n, 1) , enemy(n, -1), size(n, 1) {
    REP(i, n) parent[i] = i;
  }
  int find(int u) {
    if(u == parent[u]) return u;
    return parent[u] = find(parent[u]);
  }
  int merge(int u, int v) {
    if(u == -1 or v == -1) return max(u, v);
    u = find(u); v = find(v);
    if(u == v) return u;
    if(rank[u] > rank[v]) swap(u, v);
    if(rank[u] == rank[v]) ++rank[v];
    parent[u] = v;
    size[v] += size[u];
    return v;
  }
  bool dis(int u, int v) {
    u = find(u); v = find(v);
    if(u == v) return false;
    int a = merge(u, enemy[v]), b = merge(v, enemy[u]);
    enemy[a] = b; enemy[b] = a;
    return true;
  }
  bool ack(int u, int v) {
    u = find(u); v = find(v);
    if(enemy[u] == v) return false;
    int a = merge(u, v), b = merge(enemy[u], enemy[v]);
    enemy[a] = b;
    if(b != -1) enemy[b] = a;
    return true;
  }
  int maxParty() {
    int ret = 0;
    REP(i, parent.size())
      if(this->find(i) == i) {
        int enemy = this->enemy[i];
        if(enemy > i) continue;
        int mySize = this->size[i];
        int enemySize = (enemy == -1 ? 0 : this->size[enemy]);
        ret += max(mySize, enemySize);
      }
    return ret;
  }
};

int N, M;
int solve() {
  cin >> N >> M;
  BipartiteDisjointSet A(N);
  REP(i, M) {
    int u, v;
    string str;
    cin >> str >> u >> v;
    assert(str.size());
    if(str == "ACK") {
      if(not A.ack(u, v)) return -(i+1);
    }
    else if(str == "DIS") {
      if(not A.dis(u, v)) return -(i+1);
    }
    /*else ASF*/
  }
  return A.maxParty();
}

int main() {
  int T; cin >> T; REP(i, T) {
    int ret = solve();
    if(ret < 0) cout << "CONTRADICTION AT " << -ret << endl;
    else cout << "MAX PARTY SIZE IS " << ret << endl;
  }
  return 0;
}