#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;

vector<int> parent;
vector<int> Rank;
int groupe[10001][1];

int Find(int x)
{
    if (x == -1)
    {
        return -1;
    }
    if (x == parent[x])
    {
        return x;
    }
    else
    {
        return parent[x] = Find(parent[x]);
    }
}

void merge(int x, int y)
{
    x = Find(x);
    y = Find(y);

    if (x == y)
    {
        return;
    }

    if (Rank[x] > Rank[y]) swap(x, y);

    parent[x] = y;
    if (groupe[x][0] != -1 && groupe[y][0] != -1)
    {
        merge(groupe[x][0], groupe[y][0]);
    }
    if(groupe[x][0] == -1)
        groupe[x][0] = groupe[y][0];
    if (groupe[y][0] == -1)
        groupe[y][0] = groupe[x][0];

    if (Rank[x] == Rank[y]) Rank[y]++;
}

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

    int testN;
    cin >> testN;
    while (testN--)
    {
        int N, M;
        int res = 0;
        int visited2[10001] = { 0, };
        int resv[10001] = { 0, };
        int flag = 0;
        memset(groupe, -1, sizeof(groupe));
        cin >> N >> M;
        parent.clear();
        Rank.clear();
        parent.resize(N);

        for (int i = 0; i < N; ++i)
        {
            parent[i] = i;
        }

        Rank.resize(N);

        for (int i = 1; i <= M; ++i)
        {
            string VOE;
            int a, b;

            cin >> VOE >> a >> b;

            if (VOE == "ACK")
            {

                if (Find(groupe[Find(a)][0]) == Find(b) || Find(groupe[Find(b)][0]) == Find(a))
                {
                    cout << "CONTRADICTION AT " << i << endl;
                    flag = 1;
                    continue;
                }


                merge(a, b);
            }



            if(VOE == "DIS")
            {
            int Pa = Find(a);
            int Pb = Find(b);

                if (Pa == Pb)
                {
                    cout << "CONTRADICTION AT " << i << endl;
                    flag = 1;
                    continue;
                }

                if (groupe[Pa][0] == -1)
                    groupe[Pa][0] = Pb;

                else
                {
                    merge(groupe[Pa][0], Pb);
                }

                if (groupe[Pb][0] == -1)
                {
                    groupe[Pb][0] = a;
                }
                else
                {
                    merge(groupe[Pb][0], Pa);
                }
            }
        }

        for (int i = 0; i < N; ++i)
        {
            resv[Find(i)]++;
        }

            for (int i = 0; i < N; ++i)
            {
                int k = Find(i);
                if (!visited2[k])
                {
                    visited2[k] = 1;
                    if (groupe[k][0] != -1) {

                        res += max(resv[k], resv[Find(groupe[k][0])]);
                        visited2[k] = visited2[Find(groupe[k][0])] = 1;
                    }

                    else
                    {
                        res += resv[k];
                    }

                }

            }
            if(flag != 1)
                cout <<"MAX PARTY SIZE IS " << res << endl;
    }
}