Battleground Preservation

The people of Earth are grateful to Iron Man, Black Widow, the Hulk, and all the other superheroes, but the damage their battles inflict on the very cities they protect is severe. Over nearly 100 years of these battles there have been countless wins and losses. Whenever a new villain appears, it is assumed that a new battle must be fought. Fighting so many battles over and over, however, has been judged neither safe nor economical. A task force was therefore formed to build a database of past battles, use it to predict the winner of an upcoming battle, and — whenever possible — declare a winner before the fight (and the citywide destruction it would cause) ever takes place.

The rules they settled on are as follows:

1. Each battle in the database records who won, who lost, and the cost of victory as an integer.

2. We use the database of battles to infer the outcomes of other battles.

   • If X defeated B and B defeated Y, we treat it as if X defeated Y, with a cost of victory equal to (X-vs-B cost) + (B-vs-Y cost).
   • Such chains may grow arbitrarily long: if X beat A, A beat B, B beat C, and C beat Y, we treat it as X defeating Y, with a cost equal to the sum of the individual battle costs.
   • If there are two chains between X and Y, we use the one with the lower total cost of victory.

   From now on, "X defeated Y" may mean a direct battle between the two, or a chain of battles as described above.

3. If X has defeated Y and Y has never defeated X, we declare that X will defeat Y again.

4. If X beat Y but Y also beat X, we decide the winner by cost of victory: the one who won with the lower cost is declared the winner of the new battle. For example, if (a) Loki beat Thor with a cost of 27 and (b) Thor beat Loki with a cost of 18, then if Thor and Loki wanted to battle again we would declare Thor the winner.

5. If there have never been any battles or battle chains between X and Y, they must actually fight.

6. If the lowest cost for X to beat Y is exactly equal to the lowest cost for Y to beat X, they must actually fight.

The first line of input contains the number of test cases $T$ ($T < 100$). Each test case is given on two lines. The first line begins with the number of combatants ($< 100$) and the number of previous battles ($< 1000$), followed by those battles as triples "Combatant1 Combatant2 CostOfVictory" (meaning Combatant1 defeated Combatant2 at that cost). The second line gives the two combatants of the new battle as "Combatant1 Combatant2".

For each test case, output the name of the winner of the new battle on its own line. If the two must actually fight, output FIGHT! instead.