Description:
This is an interactive problem.
After getting AC after 13 Time Limit Exceeded verdicts on a geometry problem, Kuroni went to an Italian restaurant to celebrate this holy achievement. Unfortunately, the excess sauce disoriented him, and he's now lost!
The United States of America can be modeled as a tree (why though) with $$$n$$$ vertices. The tree is rooted at vertex $$$r$$$, wherein lies Kuroni's hotel.
Kuroni has a phone app designed to help him in such emergency cases. To use the app, he has to input two vertices $$$u$$$ and $$$v$$$, and it'll return a vertex $$$w$$$, which is the lowest common ancestor of those two vertices.
However, since the phone's battery has been almost drained out from live-streaming Kuroni's celebration party, he could only use the app at most $$$\lfloor \frac{n}{2} \rfloor$$$ times. After that, the phone would die and there will be nothing left to help our dear friend! :(
As the night is cold and dark, Kuroni needs to get back, so that he can reunite with his comfy bed and pillow(s). Can you help him figure out his hotel's location?
Input Format:
None
Output Format:
None
Note:
Note that the example interaction contains extra empty lines so that it's easier to read. The real interaction doesn't contain any empty lines and you shouldn't print any extra empty lines as well.
The image below demonstrates the tree in the sample test: