플랑크톤 먹이

수족관에 사는 해양 척추동물과 무척추동물에게 먹일 플랑크톤 먹이를 모두 직접 배양할 수 있는 동물원은 많지 않다. 어떤 동물원은 구하기 어려운 특정 먹이가 한동안 부족하고, 반대로 당장 쓸 일이 없는 다른 먹이는 창고에 잔뜩 쌓아 두기도 한다.

열수구를 갖춘 새 수족관 공사가 끝나가는 지금, 원장은 특정 먹이가 급하게 필요하다. 다행히 다른 동물원의 동료가 여러 교환 제안을 보내왔고, 원장은 긴 통화를 여러 번 거쳐 제안 목록을 완성했다. 목록을 보니 원하는 먹이를 얻으려면 여러 단계를 거쳐야 할 수도 있다. 먼저 창고에 남아도는 종류 A를 다른 종류 B로 바꾸고, B는 전혀 필요 없지만 또 다른 동물원에서 종류 C로 바꾸고, 이런 식으로 교환을 이어 가다가 마지막 교환에서 원하는 종류를 받는 식이다.

원장은 목록만 보고는 원하는 교환 사슬이 정말 있는지 알 수 없어서 경제 담당 부원장을 불렀다. 부원장은 목록을 꼼꼼히 살핀 뒤 이렇게 말했다.

"동물원이 교환으로 내주는 먹이의 양은 받는 양보다 많을 때도 있고 적을 때도 있습니다. 물론 먹이 종류와 그 동물원의 인심에 달렸지요. 원하는 교환 사슬이 있는지는 지금 말씀드릴 수 없습니다. 다만 사슬이 있다면, 우리가 가진 먹이를 조금만 넣고도 원하는 먹이를 이론상 무한히 얻도록 제안을 엮을 수 있을지도 모릅니다. 그 가능성까지 모두 확인해야 합니다."

다른 동물원의 제안 목록이 주어진다. 필요 없는 먹이를 유한한 양만 투입해서 필요한 먹이를 이론상 무한히 얻는 교환 순서를 짤 수 있는지 판정하라. 다른 동물원의 재고는 무한하다고 가정하고, 각 제안에 따른 교환은 몇 번이든 할 수 있다.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 양의 정수 네 개 $T$, $F$, $F_u$, $F_n$이 주어진다. $T$는 교환 제안의 개수, $F$는 먹이 종류의 개수다. 먹이 종류에는 1부터 $F$까지 번호가 붙는다. $F_u$는 동물원이 내놓는, 필요 없는 먹이의 번호이고 $F_n$은 교환으로 얻으려는 먹이의 번호다.

이어서 $T$개의 줄에 제안이 하나씩 주어진다. 각 줄은 세 값 $F_r$, $F_g$, $U$로 이루어진다. $F_r$과 $F_g$는 먹이 종류의 번호다. $U$는 제안한 동물원이 $F_r$ 종류 1단위를 받고 내주는 $F_g$ 종류 먹이의 단위 수에 자연로그를 취한 값이다. 동물원에서 다루는 동물은 크기 차이가 커서 로그를 즐겨 쓴다. $U$는 소수점 아래 자릿수가 3 이하인 소수이고, 절댓값은 1000 이하다. 제안한 동물원이 어디인지는 문제를 푸는 데 필요 없어서 지워 두었다. $T$는 10000 이하, $F$는 5000 이하다.

입력의 끝에는 0이 네 개 있는 줄이 주어진다.

각 테스트 케이스마다 "TRUE" 또는 "FALSE"를 한 줄에 출력한다. 필요 없는 먹이를 유한한 양만 투입해서 필요한 먹이를 이론상 무한히 얻도록 교환을 엮을 수 있으면 "TRUE"를, 그렇지 않으면 "FALSE"를 출력한다.