34040번 - 오버클럭 스페셜 저지

문제

기말고사가 막 끝난 tapris는 공장 시뮬레이션 게임을 하기 위해 컴퓨터 앞에 앉았다.

공장 시뮬레이션 게임에서 각 공장은 다음과 같이 동작한다.

• $i$번 공장은 분당 $I_i$개의 아이템을 투입해 분당 $O_i$개의 변환된 아이템을 산출한다. 즉 분당 투입량은 $I_i$이며, 분당 산출량은 $O_i$이다.
• $I_i=0$ 이면 투입하는 아이템 없이 아이템을 산출하는 공장이라는 뜻이며, $O_i=0$ 이면 산출하는 아이템 없이 아이템을 투입하는 공장이라는 뜻이다.
• 투입하는 아이템도 없고 산출하는 아이템도 없는 공장은 존재하지 않는다. 즉 $I_i = 0$ 이면서 $O_i = 0$ 인 공장은 존재하지 않는다.
• $i$번 공장에서 산출된 아이템들은 모두 $D_i$번 공장에 투입된다. $O_i=0$ 인 경우, $D_i$는 정의되지 않는다.

공장 시뮬레이션 게임에서 자동화를 위한 목표는 각 공장에 대해 분당 투입량이 다른 공장에서 산출되어 투입되는 아이템 개수의 합과 같도록 만드는 것이다. 만약 분당 투입량과 다른 공장에서 산출되어 투입되는 아이템 개수의 합이 같지 않다면, 시간이 지나 공장은 정상적으로 작동하지 않고 멈추게 된다.

tapris는 자동화를 위해 이미 존재하는 $N$개의 공장 외의 새 공장을 더 지으려고 했지만 공간이 부족해 오버클럭 기능으로 모든 공장을 멈추지 않게 만들려고 한다. 오버클럭 기능은 다음과 같이 동작한다.

• 오버클럭 배율 $K_i$를 적용하면 $i$번 공장의 분당 투입량과 분당 산출량이 모두 $K_i$배가 된다.
• 배율은 항상 양의 정수여야 하고 공장마다 독립적으로 선택할 수 있다.

다시 말해서, 모든 각 $i$번 공장에 대해 $i$번 공장에 투입되는 아이템이 $j$번 공장에서 산출된다고 할 때 다음 식을 만족해야 한다.

$$ \sum_{j: D_j = i} (O_j \times K_j) = I_i \times K_i \quad (i = 1, \cdots, n) $$

tapris를 도와 오버클럭 기능을 통해 모든 공장이 정상적으로 돌아가도록 할 수 있는지 확인해 보자.

입력

첫째 줄에 존재하는 공장의 수 $N$이 주어진다.

그다음 줄부터 $N$개의 줄에 걸쳐 $i$번 공장의 분당 입력 아이템 수 $I_i,ドル 분당 출력 아이템 수 $O_i,ドル $O_i$가 0ドル$이 아니라면 출력부와 이어진 공장의 번호 $D_i$가 주어진다.

출력

모든 공장이 돌아가는 경우가 존재한다면, 그중 하나를 $N$개의 줄에 걸쳐 각 1ドル$번부터 $N$번 공장까지 오버클럭 배율 $K_i$를 출력한다.

불가능한 경우, 첫째 줄에 stop을 출력한다.

제한

• 1ドル \leq N \leq 10$
• 0ドル \leq I_i,O_i \leq 10$
• 1ドル \leq D_i \leq N$
• 1ドル \leq K_i \leq 2^{31}-1$

입력으로 주어지는 수는 모두 정수이다.

힌트