Cocktail

To make a cocktail, N ingredients must be mixed. The exact amounts are unknown, but the mass ratios for N-1 pairs of ingredients are known.

Each ratio is given in the form a b p q. It means that the mass of ingredient a divided by the mass of ingredient b is p/q. The given N-1 ratios are sufficient to determine the relative amounts of all ingredients.

Every ingredient mass must be an integer, and the total mass must be greater than 0. Find the masses of ingredients 0 through N-1 so that all ratios are satisfied and the sum of the masses is as small as possible.

The first line contains the number of ingredients N. N is a positive integer no greater than 10.

Each of the next N-1 lines contains one ingredient-pair ratio in the form a b p q. Ingredients are numbered from 0 to N-1. a and b are integers between 0 and N-1, inclusive, and p and q are positive integers no greater than 9.

Print the required masses of ingredients 0 through N-1, in order, separated by spaces.