시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 27 13 13 54.167%

문제

과학에서 단위는 어디에서나 존재한다. 물리에서 단위는 거리(미터, 키로미터 등), 무게(키로그램, 그램 등), 그리고 다른 많은 양을 축정하는데 사용한다. 컴퓨터 과학자들은 용량의 단위(키로바이트, 메가바이트, ...)를 만들어 사용하고 있다. 당신은 여러 단위들이 주어질 때 그들의 변환 팩터를 찾는 프로그램을 작성하고자 한다.

여러 단위간의 관계를 표현하는 방법은 여러가지가, 그러나 여전히 같은 것을 의미하며, 존재한다. 예를 들자면 미터계에 존재하는 단위는 다음 페어로 정의될 수 있다: 1km = 1000m, 1m = 100cm, 1cm = 10mm. 다른 방법으로는: 1km = 100000cm, 1km = 1000000mm, 1m = 1000mm 이 있다. 두 표현법에서는 모두 똑같은 단위간의 관계를 유추할 수 있다: 1km = 1000m = 100000cm = 1000000mm.

이 문제에서 당신은 단위를 큰 순서에서 작은 순서대로 정렬하고 싶다. 예제로 cm, km, m, mm중에서 km이 가장 큰 단위이며 이유는 1km이 1cm, 1m, 1mm보다 크기 때문이다. 남은 단위들도 같은 방법으로 정렬될 수 있다. 이 예제에 대한 답은 km m cm mm이다.

이 문제에서 단위간 크기 차이는 정수배로만 나게 된다. 그렇기 때문에 1인치 = 2.54cm같은 단위는 고려하지 않아도 된다. 또한 언제나 큰 단위가 작은 단위의 몇 배로 표현되도록 입력이 주어진다.

입력

여러개의 테스트 케이스가 주어진다. 각 테스트 케이스는 유닛의 가짓수 N(2 <= N <= 10)으로 시작한다. 이어지는 줄에는 N개의 대소문자가 구분되는 단위들이 주어지며 각 단위는 최대 5글자이다. 이어지는 N - 1개의 줄에는 서로 다른 두 단위의 관계가 주어진다. 입력 형식은 "단위의 이름" "=" "1보다 큰 정수" "왼쪽 단위보다 작은 오른쪽 단위의 이름" 순이다. 각 줄은 오른쪽의 작은 단위와 왼쪽 큰 단위가 몇 배 차이가 나는지를 설명한다. 각 단위는 N - 1줄중에 한번 이상 등장하며 주어진 입력만으로 전 단위간의 관계가 파악 가능하도록 주어진다. 단위간의 관계는 (2^31 - 1) 배보다 같거나 작은 차이가 나도록 구성되어 있다.

입력으로 0이 주어지는 테스트 케이스에서 입력은 종료된다.

출력

각 테스트 케이스에 대해서 한 줄에 걸쳐 단위들의 관계를 출력한다. 단위들은 왼쪽에서 오른쪽으로, 높은 단위에서 낮은 단위로 정렬되어 있어야 하며 가장 왼쪽의 단위가 1일 때 나머지 단위들은 몇인지를 "=" 기호를 통해서 나열한다.

예제 입력

4
km m mm cm
km = 1000 m
m = 100 cm
cm = 10 mm
4
m mm cm km
km = 100000 cm
km = 1000000 mm
m = 1000 mm
6
MiB Mib KiB Kib B b
B = 8 b
MiB = 1024 KiB
KiB = 1024 B
Mib = 1048576 b
Mib = 1024 Kib
6
Kib B MiB Mib KiB b
B = 8 b
MiB = 1048576 B
MiB = 1024 KiB
MiB = 8192 Kib
MiB = 8 Mib
0

예제 출력

1km = 1000m = 100000cm = 1000000mm
1km = 1000m = 100000cm = 1000000mm
1MiB = 8Mib = 1024KiB = 8192Kib = 1048576B = 8388608b
1MiB = 8Mib = 1024KiB = 8192Kib = 1048576B = 8388608b

힌트