#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
#include <numeric>
using namespace std;

#define f first
#define s second
#define mp make_pair
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define forit(it,S) for(__typeof(S.begin()) it = S.begin(); it != S.end(); ++it)
#ifdef WIN32
    #define I64d "%I64d"
#else
    #define I64d "%lld"
#endif

typedef long long ll;
typedef vector <int> vi;
const int maxn = (int)3e4;

pair<int, pair<int, int> > e[maxn];
int emp[maxn];
int d[110][110];
long long a[110][402];
int n, m;

bool Ok(int m) {


    for (int i = 1; i <= n; ++i)
        emp[i] = false;

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < 400; ++j)
            a[i][j] = 0;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            d[i][j] = (i == j);

    for (int i = 0; i < m; ++i) {
        int u = e[i].s.f, v = e[i].s.s;

        if (e[i].f == 1)
            d[u][v] = 1;

        if (e[i].f == 2)
            d[u][v] = d[v][u] = 1;
    }

    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                d[i][j] |= (d[i][k] & d[k][j]);

    for (int i = 0; i < m; ++i) if (e[i].f == 3) {
        int u = e[i].s.f, v = e[i].s.s;
        if (d[u][v] && d[v][u]) return false;
    }

    int k = 0;
    for (int i = 0; i < m; ++i) if (e[i].f == 5) {
        int u = e[i].s.f, v = e[i].s.s;
        ++k;
        for (int t = 1; t <= n; ++t)
            if (d[u][t] || d[v][t]) {
                a[t][k >> 5] |= (1ll << (k & 31));
            }
    }

    for (int i = 0; i < m; ++i) if (e[i].f == 4) {
        int u = e[i].s.f, v = e[i].s.s;

        for (int j = 0; j < 400; ++j)
            if ((a[u][j] & a[v][j]) > 0) return false;

        if (!d[u][v]) swap(u, v);
        if (!d[u][v]) continue;

        emp[u] = true;
        for (int t = 1; t <= n; ++t)
            if (d[t][u]) emp[t] = true;
    }

    for (int i = 0; i < m; ++i) if (e[i].f == 3) {
        int u = e[i].s.f, v = e[i].s.s;
        if (emp[u] && emp[v]) return false;
    }


    return true;


}
void Solve() {

    for (int i = 0; i < m; ++i) {
        int type, u, v;
        scanf("%d%d%d", &type, &u, &v);
        e[i] = mp(type, mp(u, v));
    }

    int le = 0, ri = m;
    while (ri - le > 1) {
        int mid = (le + ri) >> 1;
        if (Ok(mid + 1)) le = mid; else
        ri = mid;
    }
    printf("%d\n", le + 1);
}
int main() {

    for (int test = 1;;++test) {
        scanf("%d%d", &n, &m);
        if (n == 0) break;
        Solve();
    }
    return 0;
}