IMPUNITS - Imperial Units

As you may know, there are currently two main sets of measurement units in the world: the metric system and the imperial system. The imperial system receives its name from the British empire, which was the place of its invention and its main user until recently. Nowadays, Britain’s heir, the United States of America, is the only country where a variation of the imperial system is the official measurement system.

For a particular magnitude, in a given measurement system there are N different units U1, U2, ... UN (the number of units depends on both the magnitude and the system). For every i (1 ≤ i ≤ N − 1), a certain number of Ui is equivalent to a certain number of Ui+1. In the metric system we always have that 1Ui is equivalent to 10Ui+1. For instance, 1 decimeter is equivalent to 10 centimeters, 1 gram is equivalent to 10 decigrams, and 1 decaliter is equivalent to 10 liters. On the contrary, in some variations of the imperial system we may have other positive integers instead of 1 and 10. For instance, 32 drams are equivalent to 875 grains.

Since you were born and raised using the much more sensible metric system, you need help learning the imperial system and its variations. You want to be able to transform directly from U1 to UN, that is, you need to know that a certain number of U1 is equivalent to a certain number of UN. To ease further calculations, you want to express the equivalence using only integers values, and these values must be as small as possible.

Input

Each test case is described using several lines. The first line contains an integer N indicating the number of units in the measurement system (2 ≤ N ≤ 10). Line i of the next N − 1 lines describes the relationship between units Ui and Ui+1 with two integers Ai and Bi representing that Ai Ui is equivalent to Bi Ui+1 (1 ≤ Ai < Bi ≤ 100). The end of input is indicated with a line containing a single −1.

Output

For each test case, output a single line with two positive integers C and D representing that CU1 is equivalent to DUN. If there are several alternatives, choose the minimum possible value for C.

Example

Input: 
5
1 2
2 3
3 4
2 5
2
6 9
-1

Output: 
1 10
2 3

Added by:Pablo Ariel Heiber
Date:2010-09-27
Time limit:0.307s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC VB.NET
Resource:FCEyN UBA ICPC Selection 2010

hide comments
2015-09-30 07:39:59 rahul_verma
AC in first Go....
2015-08-21 23:27:36 ram
Easy problem :)
Equivalent to balancing chemical equations..!!
2015-01-28 19:31:42 The Arrow
my 50th :-)
2014-04-30 04:53:29 Bharath Reddy
Tutorial problem..
2013-08-10 21:15:05 John Stephanus Peter
i don't know why i keep getting tle but i am sure my code should not be slow :(
2012-12-19 21:18:47 Paul Draper
You may also assume that both the product of all Ai and the product of all Bi are less than 2^63.
2011-05-10 10:12:04 Piotr KÄ…kol
Use long long int. ;-)
2011-01-11 16:06:38 Zvonimir
why do my program gets WA???
i believe the solution is simply to multiply all these fractions( ai / bi )
and to shrink them using gcd? isnt it correct?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.