#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

struct UFDS {
    int n;
    vector<int> info;

    UFDS() {}

    UFDS(int _n) { init(_n); }

    void init(int _n) {
        n = _n;
        info.assign(n, -1);
    }

    int get(int x) {
        if (info[x] < 0) return x;
        return info[x] = get(info[x]);
    }

    bool unite(int x, int y) {
        x = get(x), y = get(y);
        if (x == y) return false;

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

        info[x] += info[y];
        info[y] = x;

        return true;
    }

    bool connected(int x, int y) { return get(x) == get(y); }
};

struct two_colouring {
    int n;
    UFDS ufds;
    vector<int> answer, in_answer;

    two_colouring(int _n) { init(_n); }

    void init(int _n) {
        n = _n;
        ufds.init(2 * n);
    }

    void add_clause_equal(int x, int y) {
        ufds.unite(x, y);
        ufds.unite(x + n, y + n);
    }

    void add_clause_opposite(int x, int y) {
        ufds.unite(x, y + n);
        ufds.unite(x + n, y);
    }

    bool satisfiable() {
        for (int i = 0; i < n; i++)
            if (ufds.connected(i, i + n)) return false;

        return true;
    }

    // Construct an answer where we minimise the number of "which" values in each component
    // which is either 1 or 0
    void construct_answer(int which) {
        answer.resize(n);
        in_answer.assign(2 * n, 0);
        vector<int> cnt(2 * n, 0);

        for (int i = 0; i < 2 * n; i++)
            cnt[ufds.get(i)] += (i > n) ^ which;

        for (int i = 0; i < n; i++) {
            int cur = ufds.get(i), complement = ufds.get(i + n);

            if (in_answer[cur] || in_answer[complement])
                continue;

            if (cnt[cur] < cnt[complement])
                in_answer[cur] = true;
            else
                in_answer[complement] = true;
        }

        for (int i = 0; i < n; i++)
            answer[i] = (in_answer[ufds.get(i)] ? 1 : 0);
    }
};

const int MXN = 5e6 + 6, INF = 1e9 + 5;

void solve() {
    int N, Q;
    cin >> N >> Q;

    two_colouring solver(N);

    while (Q--) {
        int type, u, v;
        cin >> type >> u >> v;
        u--, v--;

        if (type == 1) {
            solver.add_clause_opposite(u, v);
        } else {
            solver.add_clause_equal(u, v);
        }
    }

    if (!solver.satisfiable()) {
        cout << "-1\n";
        return;
    }

    solver.construct_answer(1);

    int ans = 0;
    for (const auto &x : solver.answer)
        ans += !x;

    cout << ans << "\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    cin >> TC;
    while (TC--) solve();
}