Menji is lost and everyone misses him. It’s your job to find him!
There is a binary tree , consisting of vertices, and each edge of tree is of length . Menji is hiding at vertex . You know the structure of the tree. However, you don’t know .
To find , you can send signals. You can select a vertex and select a signal strength , then send a signal of strength from vertex . If the distance between and is no more than , Menji will receive the signal and send a signal back, and you will receive the signal. Otherwise, you won’t receive anything.
Sending signals is slow, and you are in a hurry, so please determine the position of Menji in no more than signals.
Interaction Protocol
The input contains multiple testcases. The first line of the input contains an integer (), the number of testcases.
For each testcase, the first line contains an integer (), the number of vertices in the tree.
The second line contains integers (), where is the parent of on the tree. The tree is rooted at vertex .
It is guaranteed that the tree is a binary tree, that is, there doesn’t exist , such that .
To send a signal, print a single line in the following format:
: Indicate that you create a signal at vertex with strength . You need to ensure . Then you have to read an integer (). If you received the signal, or equivalently, , then , otherwise .
To report the answer, print a single line in the following format:
: Indicate that you have found . You need to move on to the next testcase after printing this, or terminate if there’s no more.
For each testcase, you can send at most signals. Reporting the answer does not count as sending a signal.
If you send more than signals, or the signal you sent is malformed, or the answer you reported is incorrect, then the interaction will end and you will receive Wrong answer verdict.
Note that the interactor is adaptive, meaning that the answer may change depending on your queries as long as it remains consistent with the constraints and the answers to the previous queries.
It’s guaranteed that the sum of over all testcases does not exceed .
After printing each line do not forget to output the end of line and flush the output. You may use fflush(stdout) or cout.flush() to flush the stream for , use System.out.flush() for Java and stdout.flush() for Python.
