1 /*--------------------------------------------------------------------------------------*/  2   3 #include <algorithm>  4 #include <iostream>  5 #include <cstring>  6 #include <ctype.h>  7 #include <cstdlib>  8 #include <cstdio>  9 #include <vector> 10 #include <string> 11 #include <queue> 12 #include <stack> 13 #include <cmath> 14 #include <set> 15 #include <map> 16  17 //debug function for a N*M array 18 #define debug_map(N,M,G) printf("\n");for(int i=0;i<(N);i++) 19 {for(int j=0;j<(M);j++){ 20 printf("%d",G[i][j]);}printf("\n");} 21 //debug function for int,float,double,etc. 22 #define debug_var(X) cout<<#X"="<<X<<endl; 23 #define LL long long 24 const int INF = 0x3f3f3f3f; 25 const LL LLINF = 0x3f3f3f3f3f3f3f3f; 26 /*--------------------------------------------------------------------------------------*/ 27 using namespace std; 28  29 int N,M,T; 30 const int maxn = 2010; 31 const int maxm = 2000010; 32 //map<int ,string > mp; 33 vector <int> save[maxn]; 34  35 struct Edge{ 36     int to,next,cap,flow; 37 }edge[maxm]; 38  39 int head[maxn],tot; 40 int uN = 0; 41 int gap[maxn],dep[maxn],pre[maxn],cur[maxn]; 42  43 void init() 44 { 45     tot = 0; 46     memset(head,-1,sizeof head); 47 } 48  49 void add_edge(int u,int v,int w,int rw = 0) 50 { 51     //printf("%d->%d %d\n",u,v,w); 52     edge[tot].to = v;edge[tot].cap = w;edge[tot].next = head[u]; 53     edge[tot].flow = 0;head[u] = tot++; 54     edge[tot].to = u;edge[tot].cap = rw;edge[tot].next = head[v]; 55     edge[tot].flow = 0;head[v] = tot++; 56 } 57 int Q[maxn]; 58 void BFS(int st,int ed) 59 { 60     memset(dep,-1,sizeof dep); 61     memset(gap,0,sizeof gap); 62     gap[0] = 1; 63     int front = 0,rear = 0; 64     dep[ed] = 0; 65     Q[rear++] = ed; 66     while(front != rear) 67     { 68         int u = Q[front++]; 69         for(int i=head[u];~i;i=edge[i].next) 70         { 71             int v = edge[i].to; 72             if(dep[v] != -1) continue; 73             Q[rear++] = v; 74             dep[v] = dep[u] + 1; 75             gap[dep[v]] ++; 76         } 77     } 78 } 79 int S[maxn]; 80  81 int sap(int st,int ed) 82 { 83     BFS(st,ed); 84     memcpy(cur,head,sizeof head); 85     int top = 0; 86     int u = st; 87  88     int ans = 0; 89     while(dep[st] < uN) 90     { 91         if(u == ed) 92         { 93             int Min = INF; 94             int inser; 95             for(int i=0;i<top;i++) 96             { 97                 if(Min > edge[S[i]].cap - edge[S[i] ].flow) 98                 { 99                     Min = edge[S[i]].cap - edge[S[i]].flow;100                     inser=i;101                 }102             }103             for(int i=0;i<top;i++)104             {105                 edge[S[i]].flow += Min;106                 edge[S[i]^1].flow -= Min;107             }108             ans += Min;109             top = inser;110             u = edge[S[top]^1].to;111             continue;112         }113         bool flag = false;114         int v;115         for(int i=cur[u];~i;i=edge[i].next)116         {117             v = edge[i].to;118             if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u])119             {120                 flag = true;121                 cur[u] = i;122                 break;123             }124         }125         if(flag)126         {127             S[top++] = cur[u];128             u = v;129             continue;130         }131         int Min = uN;132         for(int i=head[u];~i;i=edge[i].next)133         {134             if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min)135             {136                 Min = dep[edge[i].to];137                 cur[u] = i;138             }139         }140         gap[dep[u]] --;141         if(!gap[dep[u]]) return ans;142         dep[u] = Min + 1;143         gap[dep[u] ]++;144         if(u != st) u = edge[S[--top]^1].to;145     }146     return ans;147 }148 149 int check(int mid)150 {151     uN = N+M+2;152     init();153     for(int i=0;i<N;i++)154     {155         add_edge(N+M,i,1);156         for(int j=0;j<save[i].size();j++)157         {158             add_edge(i,save[i][j]+N,1);159         }160     }161     for(int i=0;i<M;i++)162     {163         add_edge(N+i,N+M+1,mid);164     }165 166     int res = sap(N+M,N+M+1);167     //printf("mid:%d res:%d\n",mid,res);168     if(res == N) return true;169     else return false;170 }171 172 int solve()173 {174     int L = 0,R = 2*N,mid;175     while(L <= R)176     {177         mid = (L+R)>>1;178         if(check(mid))  R = mid-1;179         else L = mid+1;180     }181     //printf("%d %d\n",L,R);182     return L;183 }184 185 int main()186 {187     while(scanf("%d%d",&N,&M) && N+M)188     {189         char s[20];190         //mp.clear();191         for(int i=0;i<maxn;i++) save[i].clear();192         for(int i=0;i<N;i++)193         {194             scanf("%s",s);195             char c = getchar();196             if(c != ‘ ‘) continue;197             int num = -1;198             while((c = getchar()) && c !=‘\n‘)199             {200                 if(isdigit(c))201                 {202                     if(num == -1) num = 0;203                     num *= 10;num += c-‘0‘;204                 }205                 else if(c == ‘ ‘)206                 {207                     save[i].push_back(num);208                     num = -1;209                 }210             }211             if(num != -1) save[i].push_back(num);212         }213         if(M == 0 || N == 0) printf("0\n");214         else printf("%d\n",solve());215     }216 }