전장 보존

지구의 사람들은 아이언맨, 블랙 위도우, 헐크를 비롯한 여러 슈퍼히어로에게 고마워하지만, 이들이 도시를 지키려고 벌이는 전투가 정작 그 도시에 남기는 피해는 매우 심각하다. 지난 약 100년 동안 수많은 전투가 있었고, 각 전투마다 승자와 패자가 있었다. 새로운 악당이 나타나면 새로운 전투를 치러야 한다고 여겨진다. 그러나 이렇게 많은 전투를 매번 다시 치르는 것은 안전하지도, 경제적이지도 않다는 결론에 이르렀다. 그래서 지금까지 있었던 전투 기록을 데이터베이스로 만들어 앞으로 벌어질 전투의 승자를 예측하고, 가능하다면 실제로 싸우기 전에(그리고 그로 인한 도시 파괴가 일어나기 전에) 승자를 미리 선언하려는 대책반이 꾸려졌다.

이들이 정한 규칙은 다음과 같다.

1. 데이터베이스의 각 전투는 누가 이겼는지, 누가 졌는지, 그리고 승리에 든 비용(정수)을 알려 준다.

2. 이 전투 기록을 이용해 다른 전투의 결과를 추론한다.

   • X가 B를 이겼고 B가 Y를 이겼다면, X가 Y를 이긴 것으로 간주하고 그 승리 비용을 (X 대 B 비용) + (B 대 Y 비용)으로 둔다.
   • 이런 사슬은 얼마든지 길어질 수 있다. 예를 들어 X가 A를, A가 B를, B가 C를, C가 Y를 이겼다면 X가 Y를 이긴 것으로 보고, 그 비용은 각 전투 비용의 합으로 둔다.
   • X와 Y 사이에 두 개의 사슬이 있다면, 총 승리 비용이 더 낮은 쪽을 사용한다.

   이제부터 "X가 Y를 이겼다"고 말할 때, 이는 두 사람의 직접 대결일 수도 있고 위와 같은 전투 사슬을 통한 것일 수도 있다.

3. X가 Y를 이겼고 Y는 X를 이긴 적이 없다면, 새 전투에서도 X가 Y를 이길 것이라고 선언한다.

4. X도 Y를 이겼고 Y도 X를 이겼다면, 승리 비용으로 승자를 정한다. 즉 더 낮은 비용으로 이긴 쪽을 새 전투의 승자로 선언한다. 예를 들어 (a) 로키가 27의 비용으로 토르를 이겼고 (b) 토르가 18의 비용으로 로키를 이겼다면, 토르와 로키가 다시 싸우려 할 때 토르를 승자로 선언한다.

5. X와 Y 사이에 직접이든 사슬이든 어떤 전투 기록도 없다면, 두 사람은 실제로 싸워야 한다.

6. X가 Y를 이기는 최소 비용과 Y가 X를 이기는 최소 비용이 정확히 같다면, 두 사람은 실제로 싸워야 한다.

입력의 첫 줄에는 테스트 케이스의 수 $T$ ($T < 100$)가 주어진다. 각 테스트 케이스는 두 줄로 이루어진다. 첫 줄은 전투 참가자의 수($< 100$)와 이전 전투의 수($< 1000$)로 시작하고, 그 뒤에 이전 전투들이 "참가자1 참가자2 승리비용" 형태의 삼조로 나열된다(참가자1이 그 비용으로 참가자2를 이겼다는 뜻이다). 둘째 줄에는 새로 벌어질 전투의 두 참가자가 "참가자1 참가자2" 형태로 주어진다.

각 테스트 케이스마다 새 전투의 승자 이름을 한 줄에 출력한다. 두 사람이 실제로 싸워야 한다면 대신 FIGHT!를 출력한다.