套汇

Time Limit: 1000 ms

Memory Limit: 65535 ms

Description

套汇是指利用货币兑率的差异,把一个单位的某种货币转换为大于一个单位的同种货币的方法。 输入 输入有多组测试数据,每组测试数据的第一行为整数n(1<=n<=100),m,代表货币的种数和兑换的汇率,接着下面的m行为汇率, 每个汇率i,j,k代表1个单位的i货币可兑换k单位的j货币. 最后第一行代表起始所拥有的货币种类.

Input

输入以n为0结束

Output

如果经过若干步兑换操作(最终还必须兑换成起始时的货币类型),可以获得利润的话输出YES,否则输出NO.

Sample Input

8 14
1 2 0.6
2 1 0.6
1 5 1.5
5 1 0.6
6 1 0.7
1 6 0.8
3 1 1.1
1 3 0.9
4 7 0.86
7 4 0.86
4 8 1.5
8 4 0.6
7 8 0.96
8 7 0.96
1
0

Sample Output

NO

Hint

Source

LiChangMing & YinYaFeng

提交代码