Description

Arbitrage is the practice of profiting from differences in exchange rates. For example, $1$ dollar can be exchanged for $0.5$ pounds, $1$ pound can be exchanged for $10$ francs, and $1$ franc can be exchanged for $0.21$ dollars. Then, a clever trader can start from $1$ dollar and get $0.5 \times 10.0 \times 0.21 = 1.05$ dollars, earning a $5\%$ profit.

Your task is to write a program that reads a list of exchange rates from the input file and then determines whether arbitrage is possible or not.

Input Format

The input file contains multiple datasets. The first line of each dataset is an integer $n$ ($1 \le n \le 30$), representing the number of currencies.

The next $n$ lines each contain a string, which is the name of a currency (there will be no spaces in the names). The next line is an integer $m$, specifying the length of the exchange rate table. The following $m$ lines are each in the form $c_i, r_{i,j}, c_j$. Here, $c_i$ is the name of the source currency, the real number $r_{i,j}$ is the exchange rate from $c_i$ to $c_j$, and $c_j$ is the name of the target currency. Conversions not listed are impossible.

There is a blank line between datasets. When $n = 0$, the input ends.

Output Format

For the $i$-th dataset, output Case i: followed by Yes if arbitrage is possible, otherwise output No.

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0

Case 1: Yes
Case 2: No

Hint

Translated by ChatGPT 5