1 #include<iostream>  2 #include<cstring>  3 #include<algorithm>  4 #include<cstdio>  5 #include<queue>  6 #define INF 100000000  7 using namespace std;  8 const int N=3205;  9 const int M=1000000; 10 struct Node{ 11    int v; 12    int f; 13    int next; 14 }edge[M]; 15 int n,m,u,v,cnt,sx,ex; 16 int head[N],pre[N]; 17 int val[N][40];//根据题目要求申请 18 void init(){ 19     cnt=0; 20     memset(head,-1,sizeof(head)); 21 } 22 void add(int u,int v,int w){ 23     edge[cnt].v=v; 24     edge[cnt].f=w; 25     edge[cnt].next=head[u]; 26     head[u]=cnt++; 27     edge[cnt].f=0; 28     edge[cnt].v=u; 29     edge[cnt].next=head[v]; 30     head[v]=cnt++; 31 } 32 bool BFS(){ 33   memset(pre,0,sizeof(pre)); 34   pre[sx]=1; 35   queue<int>Q; 36   Q.push(sx); 37  while(!Q.empty()){ 38      int d=Q.front(); 39      Q.pop(); 40      for(int i=head[d];i!=-1;i=edge[i].next    ){ 41         if(edge[i].f&&!pre[edge[i].v]){ 42             pre[edge[i].v]=pre[d]+1; 43             Q.push(edge[i].v); 44         } 45      } 46   } 47  return pre[ex]>0; 48 } 49 int dinic(int flow,int ps){ 50     int f=flow; 51      if(ps==ex)return f; 52      for(int i=head[ps];i!=-1;i=edge[i].next){ 53         if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){ 54             int a=edge[i].f; 55             int t=dinic(min(a,flow),edge[i].v); 56               edge[i].f-=t; 57               edge[i^1].f+=t; 58             flow-=t; 59              if(flow<=0)break; 60         } 61  62      } 63       if(f-flow<=0)pre[ps]=-1; 64       return f-flow; 65 } 66 int solve(){ 67     int sum=0; 68     while(BFS()) 69         sum+=dinic(INF,sx); 70     return sum; 71 } 72 char str[20]; 73 int ans[N][N]; 74 int tot[N],top; 75 void build(int mid){ 76      init(); 77      for(int i=1;i<=n;i++){ 78         for(int j=1;j<=tot[i];j++){ 79             add(i+n,ans[i][j]+2*n,1); 80         } 81         add(i,i+n,1); 82         add(0,i,1); 83      } 84      for(int i=1;i<=m;i++){ 85         add(i+2*n,i+2*n+m,mid); 86         add(i+2*n+m,2*m+2*n+1,INF); 87      } 88 } 89 int as,temp; 90 int main() { 91     while(~scanf("%d%d",&n,&m)&&n) { 92          init(); 93          as=0; 94        for(int i=1;i<=n;i++){ 95           scanf("%s",str); 96           top=0; 97           while(getchar()!=‘\n‘){ 98               scanf("%d",&temp); 99               //printf("**%d\n",temp);100               ans[i][++top]=++temp;101           }102             tot[i]=top;103        }104        int l=0,r=n;105        sx=0,ex=2*n+2*m+1;106        while(l<=r){107           int mid=(l+r)/2;108           build(mid);109           if(solve()==n){110             r=mid-1;111             as=mid;112           }113           else114             l=mid+1;115        }116     printf("%d\n",as);117 118     }119     return 0;120 }