class Solution {
    public void addArc(Map<String, Map<String, Double>> graph, String vexStart, String vexEnd, double value) {
        Map<String, Double> arcMap;
        if (graph.containsKey(vexStart)) {
            arcMap = graph.get(vexStart);
        } else {
            arcMap = new HashMap<>();
        }
        arcMap.put(vexEnd, value);
        graph.put(vexStart, arcMap);
    }

    public double getValue(Map<String, Map<String, Double>> graph, String vexStart, String vexEnd, double cur, Set<String> v) {
        //if (v.contains(vexStart)) return 0.0;
        if (!graph.containsKey(vexStart) || !graph.containsKey(vexEnd)) return -1.0;
        if (vexStart.equals(vexEnd)) return cur;
        double ans = 0.0;
        v.add(vexStart);
        for (Map.Entry<String,Double> arc: graph.get(vexStart).entrySet()){
            if (!v.contains(arc.getKey())){
                 v.add(arc.getKey());

                ans = getValue(graph, arc.getKey(), vexEnd, 1.0*cur *arc.getValue(),v);
                v.remove(arc.getKey());
                 if (ans != -1.0) return ans;
            }
        }
        return -1.0;
    }

    public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {

        Map<String, Map<String, Double>> graph = new HashMap<>();

        for (int i = 0; i < equations.length; i++) {
            //add arcs for both directions
            addArc(graph, equations[i][0], equations[i][1], values[i]);
            addArc(graph, equations[i][1], equations[i][0], 1 / values[i]);
        }

        double[] answer = new double[queries.length];
        for (int i = 0; i < answer.length; i++) {
            answer[i] = getValue(graph, queries[i][0], queries[i][1],1,new HashSet<>());
        }

        return answer;
    }
}