套汇问题

Description:

套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，且1 法郎可以买到0.16美元。通过货币兑换，一个商人可以从1 美元开始买入，得到0.7×9.5×0.16=1.064美元，从而获得6.4%的利润。

给定n 种货币c₁,c₂,…..c_n的有关兑换率，试设计一个有效算法，用以确定是否存在套汇的可能性。

Input:

文件含多个测试数据项。每个测试数据项的第一行中只有1 个整数n (1<=n<=30)，表示货币总数。其后n行给出n种货币的名称。接下来的一行中有1 个整数m，表示有m种不同的货币兑换率。其后m行给出m种不同的货币兑换率，每行有3 个数据项c_i ， r_ij 和c_j ，表示货币c_i 和c_j的兑换率为 r_ij。文件最后以数字0 结束。

Output:

程序运行结束时，对每个测试数据项j，如果存在套汇的可能性则输出“Case j Yes”， 否则输出“Case j No”。

Sample Input:

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

Sample Output:

Case 1 Yes
Case 2 No

Note:

undefined

本题由旧版NOJ导入，来源：NUAA