Ant Race

4

10 votes
Problem

There once was an ant who liked mangoes. The ant, unlike other ants, lived on a mango tree. One fine day, the ant was eating a mango on a leaf of the tree. The ant's hunger was not satisfied by the mango. It saw another mango on a different leaf of the tree. However, the ant also saw a different ant approaching the mango. Each ant is travelling with the same speed. You have to find out which ant will get the mango.


INPUT:
The first line contains T, the number of test cases.
Then T test cases follow.

The first line of each test case consists of N, the number of nodes in the tree.
The next line consists of the inorder traversal of the tree in the form of numbers from 1 to N.
The next line consists of the preorder traversal of the tree in the form of numbers from 1 to N.
The next line consists of three numbers.
The first number is the index of the node on which the first ant is sitting. The second number is the index of the node on which the mango is placed. The third number is the index of the node on which the second ant is sitting.

The tree will always be a full binary tree. It is guaranteed that they will never reach the mango node at the same time.

OUTPUT:
Print "FIRST" without quotes if the first ant will reach the mango first and "SECOND" without quotes if the second ant will reach the mango first.

Constraints:
1 < T < 1000
1 <= N <= 1000

Time Limit: 1
Memory Limit: 256
Source Limit:
Editor Image

?