Chains of Conversions

facts lists conversion facts [a, b, x], each meaning that one a is worth x of b, such as ['mile', 'yard', 1760.0]. Facts work both ways (a yard is 1/1760 of a mile), and they chain together: a mile is 1,760 yards and a yard is 3 feet, so a mile is 5,280 feet.

Write convert(facts, questions) where each question is a pair [a, b] asking how many b there are in one a. Return a list with one float per question, in the same order. When the facts cannot answer a question, its answer is -1.0.

Examples

facts = [['gallon', 'quart', 4.0], ['quart', 'pint', 2.0], ['pint', 'cup', 2.0], ['hour', 'minute', 60.0]]
questions = [['gallon', 'cup'], ['cup', 'quart'], ['pint', 'pint'], ['cup', 'minute'], ['litre', 'litre']]
convert(facts, questions)  # returns [16.0, 0.25, 1.0, -1.0, -1.0]

A gallon is 4 quarts of 2 pints of 2 cups, so 16 cups. No chain of facts links cups to minutes. A unit converts to itself as 1.0, but only when it appears in some fact: 'litre' is never mentioned, so nothing is known about it.

Constraints

• Up to 3,000 facts and 6,000 questions. Every x is a positive float.
• The facts never contradict each other, and no fact names the same unit twice.
• Answers are checked after rounding to 6 decimal places, so tiny floating-point differences do not matter.