#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 105

enum Type{
	YES,
	NO,
	UNDEFINED,
};

enum Relation{
	IS_SUBSET_OF,
	EQUAL,
	DIFFERENT,
	NO_COMMON,
	HAVE_COMMON,
};

struct Info{
	Relation relation;
	int LEFT,RIGHT;
};

int N,M;
Info info[SIZE*SIZE];
Type is_Empty[SIZE],is_Subset[SIZE][SIZE],have_Common[SIZE][SIZE];
Relation relate_array[5] = {IS_SUBSET_OF,EQUAL,DIFFERENT,NO_COMMON,HAVE_COMMON};


bool func_Empty(int base){ //baseが新しく空集合であることが確定した

	//空集合の部分集合は、全て空集合でなければならない
	for(int i = 0; i < N; i++){
		if(is_Subset[i][base] == YES){
			if(is_Empty[i] == NO){

				return false;

			}else{

				is_Empty[i] = YES;
			}
		}
	}

	//空集合とHAVE_COMMONな要素があってはならない
	for(int i = 0; i < N; i++){
		if(i != base){
			if(have_Common[i][base] == YES){

				return false;

			}else{

				have_Common[i][base] = NO;
				have_Common[base][i] = NO;
			}
		}
	}

	return true;
}

bool check(int MID){

	//テーブルの初期化

	//空集合かどうか
	for(int i = 0; i < N; i++){

		is_Empty[i] = UNDEFINED;
	}

	//部分集合かどうか
	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			if(k == i){

				is_Subset[k][i] = YES;
			}
			else{

				is_Subset[k][i] = UNDEFINED;
			}
		}
	}

	//共通の要素があるかどうか
	for(int i = 0; i < N; i++){
		for(int k = 0; k < N; k++){
			have_Common[k][i] = UNDEFINED; //空集合なら、φ∩Φ = Φ
		}
	}

	//まずは、部分集合関係を演算する
	for(int i = 0; i <= MID; i++){
		if(info[i].relation == IS_SUBSET_OF){

			is_Subset[info[i].LEFT][info[i].RIGHT] = YES; //LEFTがRIGHTの部分集合

		}else if(info[i].relation == EQUAL){

			is_Subset[info[i].LEFT][info[i].RIGHT] = YES;
			is_Subset[info[i].RIGHT][info[i].LEFT] = YES;
		}
	}

	//ワーシャルフロイドで情報を伝達
	for(int mid = 0; mid < N; mid++){
		for(int start = 0; start < N; start++){
			if(is_Subset[start][mid] != YES)continue;
			for(int goal = 0; goal < N; goal++){
				if(is_Subset[mid][goal] != YES)continue;

				is_Subset[start][goal] = YES;
			}
		}
	}

	//共通要素を持つなら空集合ではない
	for(int i = 0; i <= MID; i++){
		if(info[i].relation == HAVE_COMMON){
			is_Empty[info[i].LEFT] = NO;
			is_Empty[info[i].RIGHT] = NO;

			have_Common[info[i].LEFT][info[i].RIGHT] = YES;
			have_Common[info[i].RIGHT][info[i].LEFT] = YES;

			//LEFT∩RIGHT != Φなので、[LEFTおよびLEFTとおなじもの]は[RIGHTおよびRIGHTと同じもの]とHAVE_COMMONになる
			for(int a = 0; a < N; a++){
				if(is_Subset[a][info[i].LEFT] == YES && is_Subset[info[i].LEFT][a] == YES){
					for(int b = 0; b < N; b++){
						if(is_Subset[b][info[i].RIGHT] == YES && is_Subset[info[i].RIGHT][b] == YES){

							is_Empty[a] = NO;
							is_Empty[b] = NO;

							have_Common[a][b] = YES;
							have_Common[b][a] = YES;
						}
					}
				}
			}
		}
	}

	//LEFT∩RIGHT = Φの場合を処理
	for(int i = 0; i <= MID; i++){
		if(info[i].relation == NO_COMMON){

			//LEFT∩RIGHT = Φより、A⊆LEFT,A⊆RIGHTとなるAについて、A = Φが成り立つ
			for(int k = 0; k < N; k++){
				if(is_Subset[k][info[i].LEFT] == YES && is_Subset[k][info[i].RIGHT] == YES){

					if(is_Empty[k] == NO){
						return false;
					}else{

						is_Empty[k] = YES;
						if(!func_Empty(k)){ //情報の反映
							return false;
						}
					}
				}
			}

			//矛盾
			if(have_Common[info[i].LEFT][info[i].RIGHT] == YES){

				return false;

			}else{

				have_Common[info[i].LEFT][info[i].RIGHT] = NO;
			}

			//LEFT⊆RIGHTでNO_COMMONなら、少なくともLEFTは空集合
			if(is_Subset[info[i].LEFT][info[i].RIGHT] == YES){

				if(is_Empty[info[i].LEFT] == NO){

					return false;

				}else{

					is_Empty[info[i].LEFT] = YES;
					if(!func_Empty(info[i].LEFT)){
						return false;
					}

				}
			}

			//RIGHT⊆LEFTでNO_COMMONなら、少なくともRIGHTは空集合
			if(is_Subset[info[i].RIGHT][info[i].LEFT] == YES){
				if(is_Empty[info[i].RIGHT] == NO){

					return false;

				}else{

					is_Empty[info[i].RIGHT] = YES;
					if(!func_Empty(info[i].RIGHT)){
						return false;
					}
				}
			}
		}
	}


	//DIFFERENTを確認
	for(int i = 0; i <= MID; i++){
		if(info[i].relation != DIFFERENT)continue;

		if(is_Subset[info[i].LEFT][info[i].RIGHT] == YES &&
				is_Subset[info[i].RIGHT][info[i].LEFT] == YES){

			return false;

		}else if(is_Empty[info[i].LEFT] == YES && is_Empty[info[i].RIGHT] == YES){ //両方が空集合なら不可

			return false;
		}
	}

	//emptyをもう一度確認
	for(int i = 0; i < N; i++){
		if(is_Empty[i] != YES)continue;

		//空集合の部分集合は、全て空集合でなければならない
		for(int k = 0; k < N; k++){
			if(is_Subset[k][i] == YES){
				if(is_Empty[k] == NO){

					return false;

				}else{

					is_Empty[k] = YES;
				}
			}
		}

		//空集合とHAVE_COMMONな要素があってはならない
		for(int k = 0; k < N; k++){
			if(k != i){
				if(have_Common[k][i] == YES){

					return false;

				}else{

					have_Common[k][i] = NO;
					have_Common[i][k] = NO;
				}
			}
		}
	}

	//have_Commonの情報を更新
	for(int a = 0; a < N; a++){
		for(int b = 0; b < N; b++){
			if(have_Common[a][b] != NO)continue;
			for(int c = 0; c < N; c++){
				if(is_Subset[c][a] != YES)continue;
				for(int d = 0; d < N; d++){
					if(is_Subset[d][b] != YES)continue;

					if(have_Common[c][d] == YES){
						return false;
					}else{
						have_Common[c][d] = NO;
						have_Common[d][c] = NO;
					}
				}
			}
		}
	}

	//HAVE_COMMONを最後に確認
	for(int i = 0; i <= MID; i++){
		if(info[i].relation != HAVE_COMMON)continue;

		if(have_Common[info[i].LEFT][info[i].RIGHT] == NO){

			return false;

		}else if(is_Empty[info[i].LEFT] == YES || is_Empty[info[i].RIGHT] == YES){

			return false;
		}
	}

	return true;
}

void func(){

	int command;

	for(int i = 0; i < M; i++){

		scanf("%d %d %d",&command,&info[i].LEFT,&info[i].RIGHT);

		command--;

		info[i].LEFT--;
		info[i].RIGHT--;
		info[i].relation = relate_array[command];
	}

	//2分探索で、条件を満たす最大行数を求める
	int ans = -1;
	int L = 0,R = M-1,MID = (L+R)/2;

	while(L <= R){

		if(check(MID)){

			ans = MID;
			L = MID+1;

		}else{

			R = MID-1;
		}
		MID = (L+R)/2;
	}

	printf("%d\n",ans+1);
}

int main(){

	while(true){

		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		func();
	}

	return 0;
}



Measured memory_bytes: 3424