Jack revels in transactions like these, but he limits the number of other people involved in a chain of transactions to 9 (otherwise things can get a bit out of hand). Normally Jack would use a little program he wrote to do all the necessary calculations to find the optimal deal, but he recently traded away his computer for a fine set of ivory-handled toothpicks. So Jack needs your help.
Input will consist of multiple test cases. The first line of the file will contain an integer n indicating the number of test cases in the file. Each test case will start with a line containing two strings and a positive integer m <= 50. The first string denotes the items that Jack wants, and the second string identifis the items Jack is willing to trade. After this will be m lines of the form
indicating that some friend of Jack's is willing to trade an amount a1 of item name1 for an amount a2of item name2. (Note this does not imply the friend is also willing to trade a2 of item name2 for a1 of item name1.) The values of a1 and a2 will be positive and <= 20. No person will ever need more than 2^31 - 1 items to compete a successful trade.
For each test case, output the phrase Case i: (where i is the case number starting at 1) followed by the best possible ratio that Jack can obtain. Output the ratio using 5 significant digits, rounded. Follow this by a single space and then the number of ways that Jack could obtain this ratio.
2 goldfish marbles 3 1 goldfish 2 marbles 5 shovels 3 marbles 1 goldfish 3 shovels this that 4 7 this 2 that 14 this 4 that 7 this 2 theother 1 theother 1 that
Case 1: 1.8000 1 Case 2: 0.28571 3NOTE: problem B from 2008 East Central Regional Contest.