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
hide comments
rahul_verma:
20150930 07:39:59
AC in first Go.... 

ram:
20150821 23:27:36
Easy problem :)


The Arrow:
20150128 19:31:42
my 50th :) 

Bharath Reddy:
20140430 04:53:29
Tutorial problem.. 

John Stephanus Peter:
20130810 21:15:05
i don't know why i keep getting tle but i am sure my code should not be slow :( 

Paul Draper:
20121219 21:18:47
You may also assume that both the product of all Ai and the product of all Bi are less than 2^63. 

Piotr KÄ…kol:
20110510 10:12:04
Use long long int. ;) 

Zvonimir:
20110111 16:06:38
why do my program gets WA???

Added by:  Pablo Ariel Heiber 
Date:  20100927 
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 