You are following a recipe to create your lunch.
The recipe is a mixture made by combining ingredients together in a bowl. Each ingredient will be either:
To make a mixture, you need to have all its ingredients ready, take an empty bowl and mix the ingredients in it. It is not possible to make mixtures by adding ingredients to an already-existing mixture in a bowl.
For example, if you want to make CAKE (a mixture) out of CAKEMIX (a mixture) and lies (a basic ingredient), then you must first make CAKEMIX in its own bowl, then add the CAKEMIX and lies to a second bowl to make the CAKE.
Once you have used a mixture as an ingredient and emptied the bowl it was prepared in, you can re-use that bowl for another mixture. So the number of bowls you need to prepare the recipe will depend on the order in which you decide to make mixtures.
Determine the minimum number of bowls you will need.
The first line will contain an integer C, the number of test cases in the input file.
For each test case, there will be:
The tokens on one line will be separated by single spaces.
The first mixture in a test case is the recipe you are making.
The names of mixtures are strings of between 1 and 20 UPPERCASE letters.
The names of basic ingredients are strings of between 1 and 20 lowercase letters.
Each mixture is used in exactly one other mixture, except for the recipe, which is not used in any other mixture. Each ingredient will appear at most once in the ingredient list for a mixture. No mixture will (directly or indirectly) require itself as an ingredient.
For each test case, output one line containing "Case #X: Y" where X is the number of the test case, starting from 1, and Y is the minimum number of mixing bowls required.
1 ≤ C ≤ 10
2 ≤ M ≤ 10
1 ≤ N ≤ 10
1 ≤ N ≤ 1000
In the first case, to satisfy your craving for SOUP, you follow these steps:
In the second case, you have a choice of whether to make FLAVOR or FRUIT first before mixing them with milk and icecream to make MILKSHAKE.
If we make FRUIT first, we use four bowls:
However if we make FRUIT after FLAVOR, we use three bowls: