CF1594D

// Problem: D. The Number of Imposters
// Contest: Codeforces - Codeforces Round 747 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1594/D
// Memory Limit: 256 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using a2l = array<ll, 2>;
using pll = pair<ll, ll>;
using vl = vector<ll>;

void solve()
{
    ll n, m;
    cin >> n >> m;
    vl fa(n + 1), cf(n + 1), sc1(n + 1, 1), sc2(n + 1);
    function<ll(ll)> ufind = [&](ll x) {
        if (fa[x] == 0)
            return x;
        ll old = fa[x];
        fa[x] = ufind(fa[x]);
        cf[x] = (cf[x] + cf[old]) % 2;
        return fa[x];
    };
    auto ujoin = [&](ll x, ll y, ll parity) -> bool {
        auto px = ufind(x), py = ufind(y);
        if (px == py)
            return (cf[x] + parity) % 2 == cf[y];
        ll nc = (parity + cf[y] - cf[x] + 2) % 2;
        cf[py] = nc, fa[py] = px;
        if (nc)
            sc1[px] += sc2[py], sc2[px] += sc1[py];
        else
            sc1[px] += sc1[py], sc2[px] += sc2[py];
        return true;
    };
    bool valid = true;
    for (ll i = 0, a, b; i < m; ++i) {
        string op;
        cin >> a >> b >> op;
        if (op[0] == 'i') {
            valid = valid && ujoin(a, b, 1);
        } else {
            assert(op[0] == 'c');
            valid = valid && ujoin(a, b, 0);
        }
    }
    if (!valid) {
        cout << -1 << '\n';
        return;
    }

    ll v = 0;
    for (ll i = 1; i <= n; ++i)
        if (ufind(i) == i)
            v += max(sc1[i], sc2[i]);
    cout << v << '\n';
}

int main(int argc, char **argv)
{
    ll t;
    cin >> t;
    while (t--)
        solve();
    return 0;
};