Your friend has invented a splendid cocktail consisting of N ingredients. However, she has forgotten the amount of each ingredient that goes into the recipe.
For N-1 pairs of ingredients, she remembers the proportion in which the ingredients within each pair should be added to the cocktail. Fortunately, these N-1 proportions are sufficient to restore the recipe of the entire cocktail.
You are given a String[] proportions containing the N-1 proportions. Each element is formatted "#<a> and #<b> as <p>:<q>" (quotes for clarity), which means that the mass of ingredient <a> divided by the mass of ingredient <b> in the cocktail must be equal to <p>/<q> (all ingredients are 0-indexed). Return a int[] containing exactly N elements, where the i-th element is the mass of ingredient i, such that all the given proportions are satisfied and the total mass is as small as possible. The total mass must be greater than 0. |