칵테일
면접 대비시간 제한2초메모리 제한128 MB
N개의 재료가 트리 형태로 N-1개의 질량 비율로 연결되어 있을 때, 모든 비율을 만족하는 가장 작은 양의 정수 질량들을 구합니다.
문제
어떤 칵테일을 만들기 위해 N개의 재료를 섞어야 한다. 각 재료의 정확한 양은 알려져 있지 않지만, N-1개의 재료 쌍 사이의 질량 비율은 알려져 있다.
각 비율은 a b p q 형식으로 주어진다. 이는 a번 재료의 질량을 b번 재료의 질량으로 나눈 값이 p/q라는 뜻이다. 주어지는 N-1개의 비율만으로 모든 재료 사이의 상대적인 비율을 결정할 수 있다.
모든 재료의 질량은 정수여야 하며, 전체 질량은 0보다 커야 한다. 조건을 모두 만족하면서 필요한 재료들의 질량 합이 최소가 되도록, 0번부터 N-1번 재료까지의 질량을 구하라.
입력
첫째 줄에 재료의 개수 N이 주어진다. N은 10 이하의 자연수이다.
둘째 줄부터 N-1개의 줄에 재료 쌍의 비율이 한 줄에 하나씩 a b p q 형식으로 주어진다. 재료 번호는 0번부터 N-1번까지이다. a와 b는 0 이상 N-1 이하의 정수이고, p와 q는 9 이하의 자연수이다.
출력
첫째 줄에 필요한 각 재료의 질량을 0번 재료부터 N-1번 재료까지 순서대로 공백으로 구분해 출력한다.