class Solution {
 public:
  vector<double> calcEquation(vector<vector<string>>& equations,
                              vector<double>& values,
                              vector<vector<string>>& queries) {
    vector<double> ans;
    // graph[A][B] := A / B
    unordered_map<string, unordered_map<string, double>> graph;

    for (int i = 0; i < equations.size(); ++i) {
      const string& A = equations[i][0];
      const string& B = equations[i][1];
      graph[A][B] = values[i];
      graph[B][A] = 1 / values[i];
    }

    for (const auto& q : queries) {
      const string& A = q[0];
      const string& C = q[1];
      if (!graph.count(A) || !graph.count(C))
        ans.push_back(-1);
      else
        ans.push_back(divide(graph, A, C, unordered_set<string>()));
    }

    return ans;
  }

 private:
  // return A / C
  double divide(
      const unordered_map<string, unordered_map<string, double>>& graph,
      const string& A, const string& C, unordered_set<string>&& seen) {
    if (A == C)
      return 1.0;

    seen.insert(A);

    // value := A / B
    for (const auto& [B, value] : graph.at(A)) {
      if (seen.count(B))
        continue;
      const double res = divide(graph, B, C, move(seen));  // B / C
      if (res > 0)                                         // valid result
        return value * res;  // A / C = (A / B) * (B / C)
    }

    return -1;  // invalid result
  }
};

class Solution {
  public double[] calcEquation(List<List<String>> equations, double[] values,
                               List<List<String>> queries) {
    double[] ans = new double[queries.size()];
    // graph.get(A).get(B) := A / B
    Map<String, Map<String, Double>> graph = new HashMap<>();

    // construct the graph
    for (int i = 0; i < equations.size(); ++i) {
      final String A = equations.get(i).get(0);
      final String B = equations.get(i).get(1);
      graph.putIfAbsent(A, new HashMap<>());
      graph.putIfAbsent(B, new HashMap<>());
      graph.get(A).put(B, values[i]);
      graph.get(B).put(A, 1.0 / values[i]);
    }

    for (int i = 0; i < queries.size(); ++i) {
      final String A = queries.get(i).get(0);
      final String C = queries.get(i).get(1);
      if (!graph.containsKey(A) || !graph.containsKey(C))
        ans[i] = -1.0;
      else
        ans[i] = divide(graph, A, C, new HashSet<>());
    }

    return ans;
  }

  // return A / C
  private double divide(Map<String, Map<String, Double>> graph, final String A, final String C,
                        Set<String> seen) {
    if (A.equals(C))
      return 1.0;

    seen.add(A);

    for (final String B : graph.get(A).keySet()) {
      if (seen.contains(B))
        continue;
      final double res = divide(graph, B, C, seen); // B / C
      if (res > 0)                                  // valid result
        return graph.get(A).get(B) * res;           // A / C = (A / B) * (B / C)
    }

    return -1.0; // invalid result
  }
}

class Solution:
  def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
    ans = []
    # graph[A][B] := A / B
    graph = defaultdict(dict)

    for (A, B), value in zip(equations, values):
      graph[A][B] = value
      graph[B][A] = 1 / value

    # return A / C
    def devide(A: str, C: str, seen: Set[str]) -> float:
      if A == C:
        return 1.0

      seen.add(A)

      # value := A / B
      for B, value in graph[A].items():
        if B in seen:
          continue
        res = devide(B, C, seen)  # B / C
        if res > 0:  # valid
          return value * res  # (A / B) * (B / C) = A / C

      return -1.0  # invalid

    for A, C in queries:
      if A not in graph and C not in graph:
        ans.append(-1.0)
      else:
        ans.append(devide(A, C, set()))

    return ans