二分答案，转化为判定问题。
建立有向图，$a->b$连边表示$a$是$b$的子集，至此可以处理掉$1$和$2$。
对于$5$，则往对应点的集合塞一个元素，即可满足$5$。
首先求出强连通分量进行缩点，再递推出每个集合的必备元素以及每个集合的所有子集，用bitset加速，可以做到$O(\frac{m^2}{32})$。
然后对于$4$，首先检验一下$5$造成的必备元素是否有交，然后将所有既能到$x$又能到$y$的集合都标记为空集，这一步同样可以用bitset加速，做到$O(\frac{nm}{32})$。
知道哪些集合必须是空集之后，再检查是否存在一个集合，满足它必须是空集但是却又有操作$5$的元素。
最后再检查$3$即可，如果$x$和$y$所属同一个强连通分量或两个都是空集则矛盾。
时间复杂度$O(\frac{m^2\log m}{32})$。
#include<cstdio>
const int N=105,M=10005,E=M*2;
int n,m,U,i,j,x,y,e[M][3],l,r,mid,ans;
int g[3][N],v[3][E],nxt[3][E],ed;
int d[N],vis[N],h,t,q[N],f[N],empty[N];
struct BIT{unsigned int v[M>>5];BIT(){}void clear(){for(int i=0;i<=U;i++)v[i]=0;}void set(int x){v[x>>5]^=1U<<(x&31);}void operator|=(const BIT&b){for(int i=0;i<=U;i++)v[i]|=b.v[i];}bool operator&(const BIT&b){for(int i=0;i<=U;i++)if(v[i]&b.v[i])return 1;return 0;}void pick(const BIT&b,const BIT&w){for(int i=t=0;i<=U;i++){unsigned int x=v[i]&b.v[i]&w.v[i];while(x){q[++t]=i<<5|__builtin_ctz(x&-x);x-=x&-x;}}}
}s[N],sub[N],w;
inline void add(int x,int y){v[0][++ed]=y;nxt[0][ed]=g[0][x];g[0][x]=ed;v[1][ed]=x;nxt[1][ed]=g[1][y];g[1][y]=ed;
}
inline void ADD(int x,int y){d[y]++;v[2][++ed]=y;nxt[2][ed]=g[2][x];g[2][x]=ed;}
void dfs1(int x){vis[x]=1;for(int i=g[0][x];i;i=nxt[0][i])if(!vis[v[0][i]])dfs1(v[0][i]);q[++t]=x;
}
void dfs2(int x,int y){vis[x]=0,f[x]=y,s[y]|=s[x],sub[y]|=sub[x];for(int i=g[1][x];i;i=nxt[1][i])if(vis[v[1][i]])dfs2(v[1][i],y);
}
bool check(int mid){for(U=0,i=1;i<=mid;i++)if(e[i][0]==5)U++;if(U<n)U=n;U=(U-1)>>5;w.clear();for(ed=0,i=1;i<=n;i++){g[0][i]=g[1][i]=g[2][i]=d[i]=empty[i]=0;s[i].clear();sub[i].clear();sub[i].set(i-1);w.set(i-1);}for(t=0,i=1;i<=mid;i++){x=e[i][1],y=e[i][2];if(e[i][0]==1)add(x,y);if(e[i][0]==2)add(x,y),add(y,x);if(e[i][0]==5)s[x].set(t),s[y].set(t++);}for(t=0,i=1;i<=n;i++)if(!vis[i])dfs1(i);for(i=n;i;i--)if(vis[q[i]])dfs2(q[i],q[i]);for(ed=0,i=1;i<=n;i++)for(j=g[0][i];j;j=nxt[0][j])if(f[i]!=f[v[0][j]])ADD(f[i],f[v[0][j]]);for(t=0,h=i=1;i<=n;i++)if(f[i]==i&&!d[i])q[++t]=i;while(h<=t)for(i=g[2][x=q[h++]];i;i=nxt[2][i]){s[v[2][i]]|=s[x];sub[v[2][i]]|=sub[x];if(!(--d[v[2][i]]))q[++t]=v[2][i];}for(i=1;i<=mid;i++)if(e[i][0]==4){x=f[e[i][1]],y=f[e[i][2]];if(s[x]&s[y])return 0;for(sub[x].pick(sub[y],w);t;t--)empty[q[t]+1]=1,w.set(q[t]);}for(i=1;i<=n;i++)if(f[i]==i)if((s[i]&s[i])&&empty[i])return 0;for(i=1;i<=mid;i++)if(e[i][0]==3){x=f[e[i][1]],y=f[e[i][2]];if(x==y)return 0;if(empty[x]&&empty[y])return 0;}return 1;
}
int main(){while(1){scanf("%d%d",&n,&m);if(!n)return 0;for(i=1;i<=m;i++)scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);l=1,r=m,ans=0;while(l<=r)if(check(mid=(l+r)>>1))l=(ans=mid)+1;else r=mid-1;printf("%d\n",ans);}
}
