Among_Us_INOI_2021.cpp

#include <bits/stdc++.h>
using namespace std;
// First you make it work, then you can always make it beautiful

const int N = 5e5 + 5;
vector<pair<int, int>> adj[N];
int color[N];
int c1, c2;
bool dfs(int node) {
    if(color[node] == 0) c1++;
    c2++;
    for(auto &[j, t] : adj[node]) {
        int etp = ((t == 1) ? (1 ^ color[node]) : color[node]);
        if(color[j] == -1) {
            color[j] = etp;
            if(!dfs(j)) return false;
        }
        else if(color[j] != etp) return false;
    }
    return true;
}

void solve() {
    int n, q;
    cin >> n >> q;

    if(q == 0) {
        cout << n << "\n";
        return;
    }

    for(int i=0;i<=n;i++) {
        adj[i].clear();
        color[i] = -1;
    }

    map<pair<int, int>, int> mp;
    bool flag = 0;
    for(int i=0;i<q;i++) {
        int t, u, v;
        cin >> t >> u >> v;
        if(u > v) swap(u, v);
        auto it = mp.find({u, v});
        if(it == mp.end()) {
            mp[{u, v}] = t;
        }
        else if(it != mp.end() && it->second != t) {
            flag = 1;
        }
        adj[u].push_back({v, t});
        adj[v].push_back({u, t});
    }
    if(flag) {
        cout << "-1\n";
        return;
    }

    int ans = 0;
    for(int i=1;i<=n;i++) {
        if(color[i] == -1) {
            color[i] = 0;
            c1 = 0, c2 = 0;
            if(!dfs(i)) {
                cout << "-1\n";
                return;
            }
            ans += max(c1, c2 - c1);
        }
    }

    cout << ans << "\n";

}


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

    int _;
    cin >> _;
    while (_-->0) {
        solve();
    }

    return 0;
}