题目描述

套利是利用货币汇率的差异将一种货币的一个单位转换为同一货币的多个单位。例如，假设 $1$ 美元购买 $0.5$ 英镑，$1$ 英镑购买 $10.0$ 法国法郎，$1$ 法国法郎购买 $0.21$ 美元。然后，通过转换货币，聪明的交易员可以从 $1$ 美元开始，购买 $0.5*10.0*0.21=1.05$ 美元，获利 $5\%$。

你的工作是编写一个程序，将货币汇率列表作为输入，然后确定套利是否可能。

输入格式

输入将包含一个或多个测试用例。在每个测试用例的第一行，有一个整数 $n(1≤n≤100)$，表示不同货币的数量。接下来的 $n$ 行分别包含一种货币的名称。在名称中不会出现空格。下一行包含一个整数 $m$，表示可以兑换货币的报价表。接下来 $m$ 行分别包含源货币的名称 $c_i$、汇率 $r_{ij}$ 和目标货币的名称 $c_j$。表示 $1$ 单位 $c_i$ 可以换到 $r_{ij}$ 单位的 $c_j$。没有出现在报价表中的交易是不可能的。

题目保证每个测试点的 $n$ 之和不超过 $1000$。$m$不超过 $A_n^2=n×(n-1)$，保证不重复。

两组测试数据之间有空行，输入为 0 时结束。

输出格式

对于每个测试用例，分别以 Case #: Yes 和 Case #: 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