Арбітраж#6664

Арбітраж

1 секунда

64 мегабайти

Середня

Арбітраж — це використання розбіжностей у валютних курсах, завдяки яким у результаті обміну можна перетворити одну одиницю валюти у більше ніж одну одиницю цієї ж валюти. Наприклад, нехай $1$ долар США коштує $0.5$ британських фунтів, $1$ британський фунт коштує $10.0$ французьких франків, а $1$ французький франк коштує $0.21$ доларів США. Тоді при обміні валюти розумний трейдер може за $1$ долар США придбати $0.5 \times 10.0 \times 0.21 = 1.05$ 0.5 \times 10.0 \times 0.21 = 1.05 доларів США, отримавши прибуток у $5$ відсотків.

Ваше завдання — написати програму, яка за списком курсів валют визначить, чи можливий арбітраж.

Вхідні дані

Вхідні дані складаються з одного або декількох тестових випадків. Перший рядок кожного тесту містить ціле число $n$ ( $1 \leq n \leq 30$ 1 \leq n \leq 30) — кількість різних валют. Кожен з наступних $n$ рядків містить назву однієї валюти. Назва не містить пробілів. Наступний рядок містить ціле число $m$ — кількість обмінних операцій. Кожен з наступних $m$ рядків містить назву $c_{i}$ c_i початкової валюти, дійсне число $r_{ij}$ r_{ij}, яке задає курс обміну від $c_{i}$ c_i до $c_{j}$ c_j, та назву $c_{j}$ c_j валюти, у яку здійснюється обмін. Обміни, не зазначені у таблиці, вважаються неможливими.

Тестові випадки відокремлені один від одного порожнім рядком. Ознака кінця вхідних даних — рядок, що містить $0$ замість $n$ .

Вихідні дані

Для кожного тесту вивести в окремому рядку, чи можливий арбітраж, у форматі "Case i: Yes" або "Case i: No", де $i$ — номер тесту у вхідних даних.

Приклади

Приклад 1