B'This in an interactive problem. There is an unknown tree consisting of n nodes, which has exactly one centroid. You only know n at first, and your task is to find the centroid of the tree. You can ask the distance between any two vertices for at most 2 cdot10^5 times. Note that the interactor is not adaptive. That is, the tree is fixed in each test beforehand and does not depend on your queries. A vertex is called a centroid if its removal splits the tree into subtrees with at most lfloor frac{n}{2} rfloor vertices each. The only line of the input contains an integer n ( 3 <= n <= 7.5 cdot10^4 ) -- the number of nodes in the tree. Start interaction by reading n . To ask a query about the distance between two nodes u, v ( 1 <= u, v <= n ), output "? u v". If you determine that the centroid of the tree is x , use "! x" to report. After printing a query, do not forget to output the end of a line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: Hacks are disabled in this problem. It 's guaranteed that there are at most 500 tests in this problem. Here is an image of the tree from the sample. '...