Задача №113259. Деляга Джек
Джек "— деляга высшего класса. Он готов продать что угодно за что угодно , если только сделка выйдет удачной. На днях ему пришло в голову обменять несколько агатовых шариков на пару золотых рыбок. Аманда, знакомая Джека, хотела продать ему одну золотую рыбку за 2 агатовых шарика. Однако Джек копнул глубже и обнаружил, что Чак будет рад продать 5 пластиковых лопат за три шарика, а Аманда продаёт 1 золотую рыбку за три лопаты. Таким образом, лучшая сделка "— через лопаты Чака "— выльется в 1.8 шарика за рыбку.
Джек решил выбрать наилучшую сделку подобного вида, ограничивая число транзакций девятью (иначе за ними будет сложно уследить). Обычно он пользуется для этого небольшой программой, но, продав недавно свой компьютер за набор зубочисток из слоновой кости, обратился на этот раз к вам.
В первой строке ввода записаны два названия товаров. Джек хочет обменять первый из них на второй по самому выгодному курсу. Также в первой строке записано число m ( 1 ≤ m ≤ 50 ) "— количество предложений, известных Джеку.
Следующие m строк описывают предложения в формате a <товар 1> b <товар 2> ( 1 ≤ a , b ≤ 20 ), что означает, что a первого товара можно обменять на b второго. Все a и b "— целые числа.
Для любой сделки потребуется не более 2 31 - 1 единиц любого товара.
Все названия состоят из строчных букв латинского алфавита и не превышают 10 по длине.
Гарантируется, что всегда существует хотя бы один способ обменять первый товар на второй, ограничивая число транзакций девятью.
Выведите два числа: наилучшее отношение обмена, которое может получить Джек (вещественное число с точностью не менее 5 знаков), а также количество способов, которыми можно получить такое отношение.