Арбітраж
Арбітраж - це використання розходжень у валютних курсах, завдяки якому у результаті обміну можна перетворити одну одиницю валюти у більш ніж одну одиницю цієї ж валюти. Наприклад, нехай 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- номер тесту.