class Solution {
    //使用构建图，使用HashMap存储节点和比率
    //对每个查询使用DFS查询两个节点是否存在连接，并计算比率
    
    // putIfAbsent方法 V putIfAbsent(K key, V value);
    // 如果之前 Map 中没有这个键，那么返回 null。
    // 如果之前已经有这个键了，那么返回该键之前关联的值，并且不会替换已有的值。
    HashMap<String, HashMap<String, Double>> hs = new HashMap<>();
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
            for (int i = 0; i < equations.size(); i++) {
                String u = equations.get(i).get(0);
                String v = equations.get(i).get(1);
                double k = values[i];
                // 构建图
                hs.putIfAbsent(u, new HashMap<>());
                hs.putIfAbsent(v, new HashMap<>());
                hs.get(u).put(v, k);
                hs.get(v).put(u, 1 / k);
                
            }
            double[] res = new double[queries.size()];
            for (int i = 0; i < queries.size(); i++) {
                String u = queries.get(i).get(0);
                String v = queries.get(i).get(1);
                if (!hs.containsKey(u) || !hs.containsKey(v)) {
                    res[i] = -1.0;
                } else {
                    res[i] = dfs(u, v, new HashSet<String>());
                }
            }
            return res;
    }
    
    public double dfs(String start, String end, HashSet<String> visited) {
        if (hs.get(start).containsKey(end)) { //直接包含
            return hs.get(start).get(end);
        }
        visited.add(start);
        for (Map.Entry<String, Double> neighbor : hs.get(start).entrySet()) {
            if (!visited.contains(neighbor.getKey())) {
                double path = dfs(neighbor.getKey(), end, visited);
                if (path != -1.0) {
                    return path*neighbor.getValue();
                }
            }
        }
        return -1.0;
    }
        
}