题目描述

套利（Arbitrage） 是指利用货币汇率之间的差异，将一种货币的单位转换为多于同一货币的单位。例如：

• 假设 1 美元可兑换 0.5 英镑，
• 1 英镑可兑换 10.0 法郎，
• 1 法郎可兑换 0.21 美元。
  那么，通过货币转换，一个精明的交易者可以用 1 美元兑换 $0.5 \times 10.0 \times 0.21 = 1.05$ 美元，从而获得 5% 的利润。

你的任务是编写一个程序，根据输入的货币汇率表，判断是否存在套利机会。

输入格式

• 每个测试用例的第一行是整数 $n$（$1 \leq n \leq 30$），表示货币种类数量。
• 接下来的 $n$ 行，每行是一种货币的名称（无空格）。
• 然后是一个整数 $m$，表示汇率表的行数。
• 接下来的 $m$ 行，每行包含：
  • 源货币名称 $c_i$，
  • 汇率 $r_{ij}$（从 $c_i$ 到 $c_j$ 的汇率），
  • 目标货币名称 $c_j$。
• 测试用例之间用空行分隔，输入以 $n=0$ 结束。

输出格式

对每个测试用例，输出一行：

• 如果存在套利机会，输出 Case case: Yes；
• 否则输出 Case case: No。

示例输入 1

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

示例输出 1

Case 1: Yes
Case 2: No

题目来源

Ulm Local 1996