Арбитраж - это использование расхождений в валютных курсах, благодаря которому в результате обмена можно преобразовать одну единицу валюты в более чем одну единицу этой же валюты. Например, пусть 1 доллар США стоит 0.5 британских фунтов, 1 Британский фунт стоит 10.0 французских франков, а 1 французский франк стоит 0.21 долларов США. Тогда при обмене валюты умный трейдер может за 1 доллар США приобрести 0.5 * 10.0 * 0.21 = 1.05 долларов США, получив прибыль в 5 процентов.
Напишите программу, которая по списку курсов валют определит, возможен ли арбитраж или нет.
Входные данные состоят из одного или нескольких тестов. Первая строка каждого теста содержит количество разных валют n (1 ≤ n ≤ 30). Каждая из следующих n строк содержит название валюты. Название не содержит внутри себя пробелов. В следующей строке задается размер m таблицы, следующей далее. Каждая из следующих m строк содержит название c_i исходной валюты, действительное число r_ij задающее обменный курс от c_i к c_j и название c_j валюты, в которую производится обмен. Обмен, не указанный в таблице, считается невозможным.
Тесты разделены друг от друга пустой строкой. Признак конца входных данных - значение 0 для n.
Для каждого теста вывести в отдельной строке возможен ли арбитраж в формате "Case i: Yes" или "Case i: No", где i - номер теста.