This page is still under construction.

Parts of this page are still being built. What you see may change.

Dining

Interview

Time limit1sMemory limit128 MB

Summary
Each cow likes certain foods and drinks, each item can go to one cow; maximize the number of cows that get a liked food and a liked drink.
Level

Medium7 of 10

Topics
Graph, Dynamic programming, Bit manipulation, Brute force
Solved
No attempts yet

Problem

Cows are finicky eaters: each cow will eat only certain foods and drink only certain drinks.

Farmer John has cooked meals for his cows but forgot to check the menu against their preferences. He may not be able to satisfy everyone, so he wants to serve a complete meal — one food and one drink — to as many cows as possible.

Farmer John has prepared FF types of food and DD types of drink (1≤F,D≤1001 \le F, D \le 100). Each of the NN cows (1≤N≤1001 \le N \le 100) has decided which foods she is willing to eat and which drinks she is willing to drink. Assign one food type and one drink type to each cow so as to maximize the number of cows that receive both a food and a drink they like.

Each serving of food and each serving of drink can be given to only one cow (for example, once food type 2 is assigned to some cow, no other cow may be assigned food type 2). Each cow may be assigned at most one food and at most one drink.

Input

  • Line 1: three space-separated integers NN, FF, and DD.
  • Lines 2 to N+1N+1: line i+1i+1 describes cow ii. It begins with two integers FiF_i and DiD_i — the number of foods cow ii likes and the number of drinks cow ii likes. The next FiF_i integers are the foods cow ii will eat, and the following DiD_i integers are the drinks cow ii will drink.

Output

  • A single integer: the maximum number of cows that can each be served both a food and a drink they are willing to consume.

Examples1

  1. Example 1

    Input
    4 3 3
    2 2 1 2 3 1
    2 2 2 3 1 2
    2 2 1 3 1 2
    2 1 1 3 3
    
    Expected output
    3