BAPC22-085.Imperfect Imperial Units

The input consists of:

• One line with two integers $n$ and $q$ ($1\leq n\leq 100$, $1\leq q\leq 10\,000$), the number of unit conversion equations and the number of queries to answer.

• $n$ lines, each defining a unit conversion in the format “1 <unit> = <value> <unit>”.

• $q$ lines, each with a query in the format “<value> <unit> to <unit>”.

In these formats, “<value>” is a floating-point number $v$ ($0.001 \leq v \leq 1000$, with at most $9$ digits after the decimal point) and “<unit>” is a string of at most $20$ English lowercase letters (a-z). A unit in a query is guaranteed to be defined in at least one unit conversion equation. Every unit can be converted into every other unit in at most one way.

For every query, output the value of the requested unit, or “impossible” if the query cannot be answered.

Your answers should have a relative error of at most $10^{-6}$.

Source: Benelux Algorithm Programming Contest 2022 · Author: Abe Wits · License: CC BY-SA 4.0 · Original: https://bapc.eu · Statement adapted for AlgoLens and shared under the same license. · 10 of the 36 original test cases (the largest) are omitted here to keep the problem lightweight.