// Original C++ solution (slower):
#include <cstring>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <string>

#include <iostream>



using namespace std;



const int MAXN = 1e4+10;

const int MAXG = 110;



int n,m;

int x[MAXN],op[MAXN],y[MAXN];

int f[MAXG][MAXG],g[MAXG][MAXG];

bool vis[MAXG] ;



void dfs(int u){

    int i, k;

    vis[u] = 1;

    for(i=1;i<=n;i++)

    if(g[u][i]){

        if(!vis[i]) dfs(i);

        for(k=1;k<=n;k++)

        if(f[i][k])

        f[u][k] = f[k][u] = 1;

    }

}



bool check(int mid) {

    for (int i=1; i<=n; i++)

        for (int j=1; j<=n; j++)

            f[i][j] = 0 ;

    for (int i=1; i<=n; i++) {

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

        g[i][i]=1;

    }

    for (int Q=1; Q<=mid; Q++) {

        int i = x[Q] , j = y[Q] , ope = op[Q];

        if (ope==1) g[i][j] = 1 ;

        else if (ope==2) g[i][j] = g[j][i] = 1 ;

        else if (ope==4) f[i][j] = f[j][i] = 1 ;

    }

    for (int k = 1 ; k <= n ; k++)

        for (int i = 1 ; i <= n ; i++)

            for (int j = 1 ; j <= n ; j++)

                if (g[i][k] && g[k][j]) g[i][j] = 1 ;



    memset(vis,0,sizeof(vis));

    for(int i=1;i<=n;i++)

    if(!vis[i]) dfs(i);



    for (int Q = 1 ; Q <= mid ; Q++) {

        int i = x[Q] , j = y[Q] , ope = op[Q];

        if (ope==3) {

            if (f[i][i] && f[j][j]) return false ;

            if (g[i][j] && g[j][i]) return false ;

        } else if (ope==5) {

            if (f[i][j] || f[j][i] || f[i][i] || f[j][j]) return false ;

        }

    }

    return true ;

}



int main() {

    while (~scanf("%d%d",&n,&m) && (n+m)) {

        for (int i=1; i<=m; i++) scanf("%d%d%d",&op[i],&x[i],&y[i]);

        int l=1,r=m,ans=0;

        while (l<=r) {

            int mid=l+r>>1;

            if (check(mid)) {

                ans=mid;

                l=mid+1;

            } else r=mid-1;

        }

        printf("%d\n",ans);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

#include <cctype>

using namespace std;

#define N 105

int n , m;

struct query

{

    int id , x , y;

}q[N * N];

bool g[N][N] , f[N][N];

bool Q(int x , int y)

{

    for (int i = 1 ; i <= n ; ++ i)

        if (g[x][i] && f[y][i] || g[y][i] && f[x][i])

            return 1;

    return 0;

}

bool check(int V)

{

    int i , j , k, x , y;

    memset(f , 0 , sizeof(f));

    memset(g , 0 , sizeof(g));

    for (i = 1 ; i <= n ; ++ i)

        g[i][i] = 1;

    for (i = 1 ; i <= V ; ++ i)

        if (q[i].id <= 2)

        {

            x = q[i].x , y = q[i].y;

            g[x][y] = 1;

            if (q[i].id == 2)

                g[y][x] = 1;

        }

    for (k = 1 ; k <= n ; ++ k)

        for (i = 1 ; i <= n ; ++ i) if (g[i][k])

            for (j = 1 ; j <= n ; ++ j) if (g[k][j])

                g[i][j] = 1;

    for (i = 1 ; i <= V ; ++ i)

        if (q[i].id == 4)

        {

            x = q[i].x , y = q[i].y;

           /* for (j = 1 ; j <= n ; ++ j) if (g[j][x])

                for (k = 1 ; k <= n ; ++ k) if (g[k][y])

                    f[j][k] = f[k][j] = 1;*/

            for (j = 1 ; j <= n ; ++ j) if (g[j][x])

                f[j][y] = 1;

            for (j = 1 ; j <= n ; ++ j) if (g[j][y])

                f[j][x] = 1;

        }

    for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) f[i][j] |= f[j][i];

    for (i = 1 ; i <= V ; ++ i)

    {

        x = q[i].x , y = q[i].y;

        if (q[i].id == 3) // x != y

        {//      x , y = empty           x == y

            if (g[x][y] && g[y][x])

                return 0;

            if (Q(x , x) && Q(y , y))

                return 0;

        }

        else if (q[i].id == 5) // x ins y != empty

        {    //x = empty   y = empty   x ins y == empty

            if (Q(x , x) || Q(y , y) || Q(x , y) || Q(y , x))

                return 0;

        }

    }

    return 1;

}



int main()

{

    while (scanf("%d%d",&n,&m))

    {

    	if(n == 0 && m == 0) break;

        for (int i = 1 ; i <= m ; ++ i)

           scanf("%d%d%d",&q[i].id, &q[i].x , &q[i].y);



        int top = 1 , bot = m , mid;

        while (top < bot)

        {

            mid = top + bot + 1 >> 1;

            if (check(mid))

                top = mid;

            else

                bot = mid - 1;

        }

        printf("%d\n" , top);

    }

    return 0;

}

// Fastest known solution for this problem: