package question;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Question399 {
 public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
 int size = 2*equations.size();
 Map<String, Integer> map = new HashMap<>(size);
 Union union = new Union(size);
 int index=0;
 for (int i = 0; i < equations.size(); i++) {
 List<String> equation=equations.get(i);
 String s0 = equation.get(0);
 String s1 = equation.get(1);
 if (!map.containsKey(s0)) map.put(s0, index++);
 if (!map.containsKey(s1)) map.put(s1, index++);
 union.merge(map.get(s0), map.get(s1), values[i]);
 }
 double[] res = new double[queries.size()];
 for (int i = 0; i < queries.size(); i++) {
 List<String> query = queries.get(i);
 String s0=query.get(0);
 String s1=query.get(1);
 if (!map.containsKey(s0) || !map.containsKey(s1)) {
 res[i]=-1.0;
 continue;
 }
 int x=map.get(s0);
 int y=map.get(s1);
 res[i]=union.getRes(x,y);
 }
 return res;
 }

 private static class Union {
 int[] root;
 double[] weight;

 public Union(int n) {
 root=new int[n];
 weight = new double[n];
 for (int i = 0; i < n; i++) {
 root[i]=i;
 weight[i]=1.0;
 }
 }

 public void merge(int x, int y, double value) {
 int fx=findRoot(x);
 int fy=findRoot(y);
 if (fx==fy) return;
 root[fx]=fy;
 weight[fx]=weight[y]*value/weight[x];
 }

 public int findRoot(int x) {
 if (root[x]==x) return x;
 int p = root[x];
 root[x]=findRoot(root[x]);
 weight[x]*=weight[p];
 return root[x];
 }

 public double getRes(int x, int y) {
 int fx=findRoot(x);
 int fy=findRoot(y);
 if (fx==fy) return weight[x]/weight[y];
 return -1.0;
 }
 }
}