Arbitrage#6664
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that US dollar buys British pounds, British pound buys French francs, and French franc buys US dollars. Then, by converting currencies, a clever trader can start with US dollar and buy 0.5 \times 10.0 \times 0.21 = 1.05 US dollars, making a profit of percent.
Your task is to write a program that takes a list of currency exchange rates as input and determines whether arbitrage is possible.
The input file contains one or more test cases. The first line of each test case contains an integer (1 \leq n \leq 30), representing the number of different currencies. The next lines each contain the name of one currency. Within a name, no spaces will appear. The next line contains one integer , representing the number of currency exchange rates that follow. Each of the next lines contains the name c_i of a source currency, a real number r_{ij} which represents the exchange rate from c_i to c_j, and the name c_j of the destination currency. Exchanges not listed are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero () for .
For each test case, print one line stating whether arbitrage is possible in the format "Case i: Yes" or "Case i: No", where is the number of the test case in the input.
Example 1