#include<cstdio>#include<cstring>#include<stack>#define M 2008using namespace std;struct E{ int u,v,next;}e[M<<10];int head[M],en;void initg(){ memset(head,-1,sizeof(head));en=0;}void add(int u,int v){ e[en].u=u;e[en].v=v; e[en].next=head[u];head[u]=en++;}int pre[M],subnum,subid[M],low[M],dfs_clock;stack<int > stk1;void initt(){ memset(pre,0,sizeof(pre)); memset(subid,0,sizeof(subid)); memset(low,0,sizeof(low)); dfs_clock=subnum=0;}void dfs(int u){ pre[u]=low[u]=++dfs_clock; stk1.push(u); for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].v; if(!pre[v]){ dfs(v); low[u]=min(low[u],low[v]); } else if(!subid[v]){ low[u]=min(low[u],pre[v]); } } if(pre[u]==low[u]){ subnum++; while(1){ int t1=stk1.top();stk1.pop(); subid[t1]=subnum; if(t1==u) break; } }}int va[M*10],vc[M*10],vb[M*10];void build(int m){ initg(); for(int i=0;i<m;i++){ int t1=va[i]*2; int t2=vb[i]*2; int t3=vc[i]; if(t3==0){ add(t1,t2^1); add(t2,t1^1); } else if(t3==1){ add(t1,t2); add(t2,t1); add(t1^1,t2^1);add(t2^1,t1^1); } else if(t3==2){ add(t1^1,t2); add(t2^1,t1); } }}int tarjan(int m,int n){ build(m); initt(); for(int i=0;i<2*n;i++){ if(!pre[i]) dfs(i); } for(int i=0;i<2*n;i+=2){ if(subid[i]==subid[i^1]) return 0; } return 1;}int binary(int m,int n){ int l=0,r=m,mid,tmax; tmax=0; while(r>=l){ mid=(l+r)>>1; if(tarjan(mid,n)){ tmax=mid; l=mid+1; } else{ r=mid-1; } } return tmax;}int main(){ int cas;while(~scanf("%d",&cas)){ while(cas--){ int n,m;scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ scanf("%d%d%d",&va[i],&vb[i],&vc[i]); } int ans=binary(m,n); printf("%dn",ans); } } return 0;}
