Cow Feast Assignment

Farmer John has prepared a variety of foods and drinks for his cows. However, each cow is very picky and will only eat or drink items she prefers. Farmer John has cooked F types of foods and prepared D types of drinks. In addition, he has N cows, and each cow has her own list of acceptable food types and drink types.

Each cow must receive a complete meal consisting of exactly one type of food and one type of drink that she likes. However, each food or drink can be assigned to at most one cow. Help Farmer John maximize the number of cows that can receive a complete meal.

This problem can be modeled as a network flow problem. Construct a flow network as follows:

• Create a source node s and a sink node t.
• Create nodes for each food type, each drink type, and for each cow, split into two nodes: one for the food assignment and one for the drink assignment.
• Add an edge from the source to each food node with capacity 1, and from each drink node to the sink with capacity 1.
• For each cow, add an edge from her food node to her drink node with capacity 1.
• For each cow and each food type she likes, add an edge from the corresponding food node to the cow's food node with capacity 1.
• Similarly, for each cow and each drink type she likes, add an edge from the cow's drink node to the corresponding drink node with capacity 1.

The maximum flow from s to t in this network equals the maximum number of cows that can be served a complete meal.

The network flow algorithm (e.g., Dinic's algorithm) should be used to compute the maximum flow. Note that any formulas will be represented in LaTeX format; for instance, if showing capacities, you might write \(c(e)=1\) for an edge \(e\) with capacity 1.

inputFormat

The input begins with three integers F, D, and N on a single line, where (1 \leq F, D, N \leq 100). Then, for each cow, there are three lines:

1. The first line contains two integers (a) and (b) indicating the number of food preferences and drink preferences, respectively.
2. The second line contains (a) distinct integers (each between 1 and (F)) representing the food types the cow likes.
3. The third line contains (b) distinct integers (each between 1 and (D)) representing the drink types the cow likes.

outputFormat

Output a single integer representing the maximum number of cows that can receive a complete meal (i.e., both a food and a drink they like).

sample

2 2 3
1 1
1
2
1 1
2
1
2 2
1 2
1 2

2