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?
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.
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)