class Solution {
    class Pair {
        String end;
        double val;
        public Pair(String end, double val) {
            this.end = end;
            this.val = val;
        }
    }

    class DSU {
        Map<String, Pair> parents;

        public DSU() {
            parents = new HashMap<>();
        }

        public void make_pair(String x) {
            if (!parents.containsKey(x)) {
                Pair pair = new Pair(x, 1.0);
                parents.put(x, pair);
            }
        }

        public Pair find(String x) {
            if (!parents.containsKey(x)) return null;
            
            // parents[x] == x
            if (parents.get(x).end.equals(x)) return parents.get(x);
            
            // path compression
            // parents[x] = find(parents[x])
            Pair p = parents.get(x);
            Pair pp = find(p.end);

            // update value
            parents.put(x, new Pair(pp.end, pp.val * p.val));
            return parents.get(x);
        }

        public void union(String x, String y, double val) {
            Pair px = find(x);
            Pair py = find(y);

            if (px == null || py == null) return;

            if (!px.end.equals(py.end)) {
                // px / x = valx
                // py / y = valy
                // x / y = val
                // newVal = valx / valy * val

                double valx = px.val;
                double valy = py.val;
                double newVal = valx * val / valy;
                parents.put(py.end, new Pair(px.end, newVal));
            }
        }

        public double query(String x, String y) {
            Pair px = find(x);
            Pair py = find(y);

            if (px == null || py == null) return -1.0;
            if (!px.end.equals(py.end)) return -1.0;
            if (x.equals(y)) return 1.0;

            // px / x = valx
            // px / y = valy
            // x / y = valy / valx
            return py.val / px.val;
        }
    }

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int m = equations.size();
        int n = queries.size();
        double[] answer = new double[n];
        DSU dsu = new DSU();

        for (int i = 0; i < m; i++) {
            List<String> eq = equations.get(i);
            double val = values[i];
            String x = eq.get(0);
            String y = eq.get(1);
            dsu.make_pair(x);
            dsu.make_pair(y);
            dsu.union(x, y, val);
        }

        for (int i = 0; i < n; i++) {
            List<String> q = queries.get(i);
            answer[i] = dsu.query(q.get(0), q.get(1));
        }

        return answer;
    }
}

// path compression
// parents[x] = find(parents[x])
Pair p = parents.get(x);
Pair pp = find(p.end);

// update value
parents.put(x, new Pair(pp.end, pp.val * p.val));