二分答案，转化为判定问题。
建立有向图，$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);
}
}