#include <bits/stdc++.h>

using namespace std;
const int N = 1e6 + 5, MOD = 1e9 + 7;  

int n, q;
vector<int> vv;

int t[N], x[N], u[N], y[N], v[N], k[N];

vector<int> adj[N];

inline int no(int x){
    if(x <= n) return x + n;
    return x - n;
}

inline int id(int x, int k){
    if(k) return x + n;
    return x;
}

int low[N], num[N], timedfs = 0, sccs = 0, label[N]; 
stack<int> st;

void dfs(int i, int pre){
    st.push(i);
    num[i] = low[i] = ++timedfs;
    for(int x : adj[i]){
        if(label[x]) continue;
        if(!num[x]){
            dfs(x, i);
            low[i] = min(low[i], low[x]);
        } else{
            low[i] = min(low[i], num[x]);
        }
    }
    if(low[i] == num[i]){
        int u = -1; ++sccs;
        while(u != i){
            u = st.top(); st.pop();
            label[u] = sccs;
        }
    }
}


bool check(int tt){
    timedfs = sccs = 0;
    for(int i = 1; i <= 2 * n; i++){
        num[i] = low[i] = label[i] = 0;
        adj[i].clear();
    }

    for(int i = 1; i <= tt; i++){
        if(t[i] == 1){
            adj[id(x[i], k[i] ^ 1)].push_back(id(x[i], k[i]));
            assert(x[i]);
        } else if(t[i] == 2){
            adj[x[i]].push_back(id(y[i], k[i]));
            adj[y[i]].push_back(id(x[i], k[i]));
            adj[x[i] + n].push_back(id(y[i], k[i] ^ 1));
            adj[y[i] + n].push_back(id(x[i], k[i] ^ 1));
            assert(x[i]); assert(y[i]);
        } else if(t[i] == 3){
            adj[id(x[i], u[i] ^ 1)].push_back(id(y[i], v[i]));
            adj[id(y[i], v[i] ^ 1)].push_back(id(x[i], u[i]));
            assert(x[i]); assert(y[i]);
        }
    }
    for(int i = 1; i <= 2 * n; i++){
        if(!num[i]) dfs(i, i);
    }
    for(int i = 1; i <= n; i++){    
        if(label[i] == label[n + i]) return false;
    }
    return true;
}

void solve(){
    vv.clear();
    cin >> n >> q;
    for(int i = 1; i <= q; i++){
        cin >> t[i];
        if(t[i] == 1){
            cin >> x[i] >> k[i];
        } else if(t[i] == 2){
            cin >> x[i] >> y[i] >> k[i];
        } else{
            cin >> x[i] >> u[i] >> y[i] >> v[i];
        }   
        vv.push_back(x[i]);
        vv.push_back(y[i]);
    }
    vv.push_back(0);
    sort(vv.begin(), vv.end()); vv.resize(unique(vv.begin(), vv.end()) - vv.begin());
    n = vv.size() - 1;
    for(int i = 1; i <= q; i++){
        x[i] = lower_bound(vv.begin(), vv.end(), x[i]) - vv.begin();
        y[i] = lower_bound(vv.begin(), vv.end(), y[i]) - vv.begin();
    }
    int lo = 1, hi = q, ans = -1;
    while(lo <= hi){
        int mid = (lo + hi) / 2;
        if(!check(mid)){
            ans = mid, hi = mid - 1;
        } else{
            lo = mid + 1;
        }
    }
    cout << ans << '\n';    
    for(int i = 1; i <= q; i++){
        x[i] = y[i] = k[i] = u[i] = v[i] = 0;
    }
}

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

    int t = 1; 
    cin >> t;

    while(t--){
        solve();
    }
}