Flavour Saver

Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 512M

Problem type

It's 3:59 pm which means it's closing time at the local Frozen Yogurt store and that means there are bargains to be found. This frozen yogurt vendor has a particular policy that any yogurt order that finishes a particular topping is free! Yes, free!

You and your associates, skint but sweaty they may be, are looking to minimise the collective money you spend which means maximizing the number of toppings your orders finish. But, you still have standards and preferences which means each associate will only order from a set of acceptable toppings (that happen to be one order away from being empty).

Given a list of associates' preferred toppings (all of which are one order away from being empty), can you compute the maximum number of free yogurts can be acquired by your motley crew given their preferences?

Input Specification

The first line contains three integers, \(A, F, P\), \(1 \leq A, F \leq 1000\), \(1 \leq P \leq 10^5\), the number of associates, flavours and preferences respectively. The following \(P\) lines will contain two strings \(a, p\), \(1 \leq len(a), len(p) \leq 255\), an associate's name and an acceptable topping name. All strings will comprise of English letters.

Output Specification

A single integer, the maximum number of free yogurts possible.

Sample Input 1

3 3 6
Ben cookie
Jerry chocolate
Sam cookie
Ben strawberry
Jerry strawberry
Sam chocolate

Sample Output 1


Sample Input 2

4 3 6
Ben chocolate
Bob cookie
ben chocolate
Jess cookie
Ben berry
ben berry

Sample Output 2


N.B. All names are case-sensitive and some associates may go without free frozen yogurt (this is why they're associates and not friends)


There are no comments at the moment.