#include<bits/stdc++.h> #define fst(a,b,c) for(int a=(b);a<=(c);a++) #define est(x) for(int i=hd[x],y=to[i];i;i=nt[i],y=to[i]) using namespace std; const int N=8e3+100,M=4.4e3+100; int n,m; int l[M],r[M],ord[176010]; int read(){ char in=getchar(); int x=0; while(!isdigit(in)) in=getchar(); while(isdigit(in)) x=x*10+(in^48),in=getchar(); return x; } namespace XYL{ int ans=0; int hd[N],to[M*2],nt[M*2],tot; int pot[N],num,mat[N]; bool vis[N]; void add(int x,int y){ to[++tot]=y;nt[tot]=hd[x];hd[x]=tot; to[++tot]=x;nt[tot]=hd[y];hd[y]=tot; } void build(int x,bool col){ vis[x]=1; if(col) pot[++num]=x; est(x){ if(vis[y]) continue; build(y,col^1); } } bool find(int x){ est(x){ if(!mat[y]){ mat[y]=x; return 1; } else if(find(mat[y])){ mat[x]=y; return 1; } hd[x]=nt[hd[x]]; } return 0; } void Main(){ fst(i,1,m) add(ord[l[i]],ord[r[i]]); fst(i,1,n) if(!vis[i]) build(i,1); fst(i,1,num) if(find(pot[i])) ans++; printf("%d\n",ans); } } namespace BL{ int ans; bool use[N]; void work(int x,int cnt=0){ if(x==n+1){ans=max(ans,cnt); return;} fst(i,l[x],r[x]){ if(use[ord[i]]) continue; use[ord[i]]=1; fst(j,i+1,r[x]){ if(use[ord[j]]) continue; use[ord[j]]=1; work(x+1,cnt+1); use[ord[j]]=0; } use[ord[i]]=0; } work(x+1,cnt); return; } void Main(){ work(1); printf("%d\n",ans); return; } } int main(){ // freopen("subnet.in","r",stdin); // freopen("subnet.out","w",stdout); bool flag2=1; n=read(),m=read(); fst(i,1,m){ l[i]=r[i-1]+1; r[i]=r[i-1]+read(); fst(j,l[i],r[i]) ord[j]=read(); if(r[i]-l[i]>1) flag2=0; } if(flag2) XYL::Main(); else BL::Main(); return 0; }