class Solution {
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {


        Map<String, List<String>> graph1 = new HashMap<>(); // bi-direcction
        Map<String, Double> graph = new HashMap<>(); // bi-direcction
        for (int i = 0; i < equations.size() ;i++) {
            List<String> equation = equations.get(i);
            String key1 = equation.get(0);
            String key2 = equation.get(1);
            double value = values[i];

            if (graph1.containsKey(key1) == false) {
                graph1.put(key1, new ArrayList<>());
            }
            graph1.get(key1).add(key2);
            if (graph1.containsKey(key2) == false) {
                graph1.put(key2, new ArrayList<>());
            }
            graph1.get(key2).add(key1);

            graph.put(get_key(key1, key2), value);
            graph.put(get_key(key2, key1), 1 / value);
        }

        double[] results = new double[queries.size()];
        for (int i = 0; i < queries.size() ;i++) {
            List<String> query = queries.get(i);
            String start = query.get(0);
            String end = query.get(1);

            String now = start;

            // System.out.printf("[%s ---> %s]%n", start, end);

            visited = new HashSet<>();
            Double result = find(graph1, graph, now, end);
            if (result != 0) {
                results[i] = result;
            }else {
                results[i] = -1;
            }
        }

        return results;
    }

    Set<String> visited = new HashSet<>();
    public Double find(Map<String, List<String>> graph1, Map<String, Double> graph, String now, String end) {
            if (graph1.containsKey(now) == false) {
                return 0d;
            }
            if (now.equals(end)) {
                return 1d;
            }

            String from = now;
            visited.add(now);
            boolean is_end = true;
            for (String to :graph1.get(now)) {

                if (visited.contains(to)) continue;
                is_end = false;

                Double value = graph.get(get_key(from, to));
                Double result_now = value * find(graph1, graph, to, end);
                if (result_now != 0) {
                    return result_now;
                }
                // System.out.printf("(%s->%s:%f)%n", from, to, value);
            }

            if (is_end) {
                if (now.equals(end) == false) {
                    return 0d;
                }
            }
            visited.remove(now);

            return 0d;
    }

    public String get_key(String from, String to) {
        return from + "->" + to;
    }
}