#include <cstdio> #include <queue> #include <cstring> using namespace std; struct rd{ int x; int y; int nxt; int fl; }; rd a[2000005]; int h[20005]; int n,m,qt,rts,rtt,flmx; int p[20005]; int lst[20005]; int f[20005]; int d[20005]; int vst[20005]; void addd(int ax,int ay,int afl){ a[++qt].x=ax; a[qt].y=ay; a[qt].nxt=h[ax]; a[qt].fl=afl; h[ax]=qt; } void pld(int ax,int ay,int afl){ addd(ax,ay,afl); addd(ay,ax,0); } bool spfa(int s,int t){ int i,u,v; queue <int> q; for(i=1;i<=rtt;i++){ vst[i]=0; p[i]=0; f[i]=1e9; d[i]=1e9; } d[s]=0; vst[s]=1; q.push(s); p[t]=-1; while(!q.empty()){ u=q.front(); q.pop(); vst[u]=0; for(i=h[u];i!=-1;i=a[i].nxt){ v=a[i].y; if(a[i].fl>0&&d[v]>d[u]+1){ d[v]=d[u]+1; if(!vst[v]){ q.push(v); vst[v]=1; } f[v]=min(f[u],a[i].fl); p[v]=u; lst[v]=i; } } } return p[t]!=-1; } void dinic(int s,int t){ int nw; while(spfa(s,t)){ nw=t; flmx+=f[t]; while(nw!=s){ a[lst[nw]].fl-=f[t]; a[lst[nw]^1].fl+=f[t]; nw=p[nw]; } } } int main(){ scanf("%d%d",&n,&m); int i,j,k,ax,ay; qt=-1; memset(h,-1,sizeof(h)); for(i=1;i<=m;i++){ scanf("%d",&k); scanf("%d%d",&ax,&ay); pld(ax,ay+n,1); pld(ay,ax+n,1); } rts=n*2+1; rtt=rts+1; for(i=1;i<=n;i++){ pld(i,i+n,1); pld(rts,i,1); pld(i+n,rtt,1); } dinic(rts,rtt); printf("%d\n",flmx/2); return 0; }