1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 using namespace std;  5 const int N = 1e3 + 5;  6 const int M = 1e4 + 5;  7 const int inf = 0x3f3f3f3f;  8 struct Edge {  9     int to, next, cap, flow; 10 }edge[M]; 11 int tot, head[N], gap[N], dep[N], cur[N]; 12 void init() { 13     tot = 0; 14     memset(head, -1, sizeof(head)); 15 } 16 void addedge(int u, int v, int w, int rw = 0) { 17     edge[tot].next = head[u]; edge[tot].to = v; edge[tot].cap = w; edge[tot].flow = 0; head[u] = tot++; 18     edge[tot].next = head[v]; edge[tot].to = u; edge[tot].cap = rw; edge[tot].flow = 0; head[v] = tot++; 19 } 20 int Q[N]; 21 void bfs(int start, int end) { 22     memset(dep, -1, sizeof(dep)); 23     memset(gap, 0, sizeof(gap)); 24     gap[0] = 1; 25     int front = 0, rear = 0; 26     dep[end] = 0; 27     Q[rear++] = end; 28     while(front != rear) { 29         int u = Q[front++]; 30         for(int i = head[u]; ~i; i = edge[i].next) { 31             int v = edge[i].to; 32             if(dep[v] != -1) 33                 continue; 34             Q[rear++] = v; 35             dep[v] = dep[u] + 1; 36             gap[dep[v]]++; 37         } 38     } 39 } 40 int S[N]; 41 int sap(int start, int end, int N) { 42     bfs(start, end); 43     memcpy(cur, head, sizeof(head)); 44     int top = 0; 45     int u = start; 46     int ans = 0; 47     while(dep[start] < N) { 48         if(u == end) { 49             int Min = inf; 50             int inser; 51             for(int i = 0; i < top; ++i) { 52                 if(Min > edge[S[i]].cap - edge[S[i]].flow) { 53                     Min = edge[S[i]].cap - edge[S[i]].flow; 54                     inser = i; 55                 } 56             } 57             for(int i = 0; i < top; ++i) { 58                 edge[S[i]].flow += Min; 59                 edge[S[i] ^ 1].flow -= Min; 60             } 61             ans += Min; 62             top = inser; 63             u = edge[S[top] ^ 1].to; 64             continue; 65         } 66         bool flag = false; 67         int v; 68         for(int i = cur[u]; ~i; i = edge[i].next) { 69             v = edge[i].to; 70             if(edge[i].cap - edge[i].flow && dep[v] + 1 == dep[u]) { 71                 flag = true; 72                 cur[u] = i; 73                 break; 74             } 75         } 76         if(flag) { 77             S[top++] = cur[u]; 78             u = v; 79             continue; 80         } 81         int Min = N; 82         for(int i = head[u]; ~i; i = edge[i].next) { 83             if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) { 84                 Min = dep[edge[i].to]; 85                 cur[u] = i; 86             } 87         } 88         gap[dep[u]]--; 89         if(!gap[dep[u]]) 90             return ans; 91         dep[u] = Min + 1; 92         gap[dep[u]]++; 93         if(u != start) 94             u = edge[S[--top] ^ 1].to; 95     } 96     return ans; 97 } 98  99 int main()100 {101     int n, f, d;102     while(scanf("%d %d %d", &n, &f, &d) != EOF) {103         int m1, m2, num;104         init();105         for(int k = 1; k <= n; ++k) {106             scanf("%d %d", &m1, &m2);107             for(int i = 1; i <= m1; ++i) {108                 scanf("%d", &num);109                 addedge(2 * n + num, k, 1);110             }111             for(int i = 1; i <= m2; ++i) {112                 scanf("%d", &num);113                 addedge(n + k, 2 * n + f + num, 1);114             }115         }116         for(int i = 1; i <= n; ++i) {117             addedge(i, n + i, 1);118         }119         for(int i = 1; i <= f; ++i) {120             addedge(0, 2 * n + i, 1);121         }122         for(int i = 1; i <= d; ++i) {123             addedge(2 * n + f + i, 2 * n + f + d + 1, 1);124         }125         printf("%d\n", sap(0, 2 * n + f + d + 1, 2 * n + f + d + 2));126     }127     return 0;128 }