Hotel King: Maximizing Guest Satisfaction

A hotel owner wants to become the "Hotel King" by making his hotel more personalized. The hotel has \(p\) rooms and serves \(q\) different dishes every day. Each room can only accommodate one guest and each dish can only be served to one guest.

One day, \(n\) guests arrive. Each guest specifies the set of rooms they like along with the dishes they prefer. A guest is considered satisfied if he is assigned both a room from his preferred set and a dish from his preferred set.

Your task is to assign rooms and dishes such that the number of satisfied guests is maximized.

Note: Each room and each dish can be assigned to at most one guest. It is possible that not all guests can be satisfied.

Hint: You may model the problem as a flow network. Consider splitting each customer node into two nodes (an input and an output) and then connecting rooms to customers and customers to dishes.

inputFormat

The first line contains three integers: \(p\), \(q\), and \(n\) representing the number of rooms, the number of dishes, and the number of guests respectively.

For each guest, there are two lines:

• The first line starts with an integer \(r_i\) (the number of rooms the guest likes) followed by \(r_i\) integers indicating the room numbers (each in the range \(1\) to \(p\)).
• The second line starts with an integer \(d_i\) (the number of dishes the guest likes) followed by \(d_i\) integers indicating the dish numbers (each in the range \(1\) to \(q\)).

outputFormat

Output a single integer representing the maximum number of guests that can be satisfied.

sample

3 3 4
1 1
1 1
2 1 2
1 2
1 3
1 3
1 2
1 1

3