Evaluate query ratios from equations

You are given equations of the form A / B = value where A and B are variable names (strings) and value is a positive real number.

You also receive queries of the form X / Y = ?. For each query, return the computed ratio if it can be derived from the known equations; otherwise return -1.0.

Input

• equations : list of pairs [Ai, Bi]
• values : list of doubles where values[i] corresponds to Ai / Bi
• queries : list of pairs [Xj, Yj]

Output

• Array of doubles where each element is the answer for the corresponding query.

Notes / Constraints

• Variables not appearing in any equation make related queries impossible.
• You may assume there are no contradictions.
• Aim for a graph + DFS/BFS solution.

Example

• equations = [["a","b"],["b","c"]] , values = [2.0, 3.0]
• queries = [["a","c"],["c","a"],["a","e"],["a","a"],["x","x"]]
• Output: [6.0, 1/6, -1.0, 1.0, -1.0]