#include <bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define FORR(i,a,b) for(int i=(int)(b)-1; i>=(int)(a); i--)

using ll = long long;
using pii = pair<int,int>;
using pid = pair<int,double>;

int n,m;
bool ok;
bool g[252][252];
int ty[12525], xi[12525], xj[12525];
vector<int> fook[252][252];

void f(int id){
  int s = xi[id], t = xj[id];
  if(ty[id] == 3){
    if(g[s][t] && g[t][s]){
      ok = false;
    }else if(g[s][s+n] && g[t][t+n]){
      ok = false;
    }
  }else if(ty[id] == 5){
    if(g[s][s+n] || g[t][t+n]){
      ok = false;
    }else if(g[s][t+n] && g[t][s+n]){
      ok = false;
    }
  }
}

void add_edge(int i, int j){
  if(g[i][j])return;
  g[i][j] = true;
  // (i,j) check
  for(int id : fook[i][j]){
    f(id);
  }
  // add others
  REP(s,2*n)if(g[s][i] && !g[s][j]){
    add_edge(s,j);
  }
  REP(t,2*n)if(g[j][t] && !g[i][t]){
    add_edge(i,t);
  }
  if(i+n==j){
    REP(s,n)if(g[s][i]){
      add_edge(i,s);
      add_edge(s,s+n);
      add_edge(s+n,i+n);
    }
  }
  if(i<n && j<n && g[j][j+n] && !g[j][i]){
    add_edge(i,i+n);
    add_edge(j,i);
    add_edge(i+n,j+n);
  }
}

int solve(){
  // initialize
  ok = true;
  REP(i,2*n)REP(j,2*n)g[i][j] = false;
  REP(i,2*n)REP(j,2*n)fook[i][j].clear();
  REP(i,m){
    int s = xi[i], t = xj[i];
    if(ty[i]==1){
      add_edge(s,t);
      add_edge(t+n,s+n);
    }else if(ty[i]==2){
      add_edge(s,t);
      add_edge(t+n,s+n);
      add_edge(t,s);
      add_edge(s+n,t+n);
    }else if(ty[i]==4){
      add_edge(s,t+n);
      add_edge(t,s+n);
    }else if(ty[i]==3){
      f(i);
      fook[s][s+n].push_back(i);
      fook[t][t+n].push_back(i);
      fook[s][t].push_back(i);
      fook[t][s].push_back(i);
    }else if(ty[i]==5){
      f(i);
      fook[s][s+n].push_back(i);
      fook[t][t+n].push_back(i);
      fook[s][t+n].push_back(i);
      fook[t][s+n].push_back(i);
    }
    if(!ok){
      return i;
    }
  }
  return m;
}

int naive(){
  int n2 = 1<<n;
  int ans = 0;
  REP(s,1<<n2){
    vector<int> ss(n);
    REP(i,n){
      REP(j,n2)if((j>>i&1) && (s>>j&1))ss[i] += 1<<j;
    }
    bool ok = true;
    REP(i,m){
      if(ty[i]==1){
        if((ss[xi[i]] & ss[xj[i]]) != ss[xi[i]])ok=false;
      }else if(ty[i]==2){
        if(ss[xi[i]] != ss[xj[i]])ok=false;
      }else if(ty[i]==3){
        if(ss[xi[i]] == ss[xj[i]])ok=false;
      }else if(ty[i]==4){
        if((ss[xi[i]] & ss[xj[i]]) != 0)ok=false;
      }else if(ty[i]==5){
        if((ss[xi[i]] & ss[xj[i]]) == 0)ok=false;
      }
      if(!ok){
        ans = max(ans, i);
        break;
      }
    }
    if(ok){
      ans = m;
      break;
    }
  }
  return ans;
}

int main(){
  while(false){
    n = 3;
    m = 8;
    REP(i,m){
      ty[i] = rand() % 5 + 1;
      xi[i] = rand() % n;
      xj[i] = rand() % (n-1);
      if(xj[i] >= xi[i])xj[i]++;
    }
    int ans1 = solve();
    int ans2 = naive();
    if(ans1 != ans2){
      printf("%d %d\n", n,m);
      REP(i,m)printf("%d %d %d\n",ty[i],xi[i]+1,xj[i]+1);
      printf("ans1: %d\n",ans1);
      printf("ans2: %d\n",ans2);
      return 0;
    }
  }
  while(true){
    scanf("%d%d",&n,&m);
    if(n+m==0)break;
    REP(i,m)scanf("%d%d%d",ty+i,xi+i,xj+i),xi[i]--,xj[i]--;
    printf("%d\n", solve());
  }
  return 0;
}




Measured memory_bytes: 6572