Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Lost in Binary Tree

By reborn · Limits 1s, 128 MB · Interactive

You have a rooted unweighted binary tree. But somehow you forgot which vertex was the root. Well, you can ask me. I remember. But let's play a game. In each move, you can pick a vertex and ask me the distance of that vertex from that root. And I'll tell you so. However, I'll answer no more than 2020 of your queries.

Input

The first line of input will contain an integer NN denoting the number of vertices. Following N1N - 1 lines will describe the tree. Each line will have two space-separated integers u, vu, ~v representing an edge between uu and vv.

  • 1N1051 \le N \le 10^5.
  • Vertices are numbered from 11 to NN.
  • You can be assured that the input will describe a valid tree.

Interaction

To ask a question, that is to ask how far a vertex vv is from root, print "? vv" without the quotes in a single line and flush the output. The judge will reply with an integer dd as the answer to your query. After you have figured out the root vertex rr, you can submit your answer via printing "! rr" without quotes in a single line.

After submitting the root properly, your program must quit immediately since the interactor will stop interaction and depending upon the submission you'll receive "Accepted" or "Wrong answer". If you have asked more than 2020 questions or any of your output format is wrong, the interactor will output an integer value of 1-1 and will stop interaction immediately. At any point after receiving 1-1, Your program must quit immediately and will receive "Wrong answer".

Note that submitting the root rr is not counted as one of the 2020 queries.

Sample I/O

> 4
> 1 2
> 1 3
> 1 4
< ? 1
> 1
< ? 2
> 2
< ! 3

> indicates what your program reads and < indicates what your program writes. These symbols are here to make it easy to understand. You must not print such symbols from your program.


The above figure describes the tree from input in line 1 to 4 in Sample I/O.

  • Upon asking the distance from 1 in line 5, the interactor replies with 1 in line 6.
  • Upon asking the distance from 2 in line 7, the interactor replies with 2 in line 8.
  • Upon submitting the root as 3 in line 9, the interactor quits immediately.

Notes

Since this is an interactive problem, don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf/cout in C/C++, import sys and sys.stdout.flush() in Python to flush the output. If you use some other programming language, consult it's documentation.

To learn more about Interactive Problems: https://help.toph.co/toph/interactive-problems

Discussion

Statistics


60% Solution Ratio

nuipqiunEarliest, 11M ago

Deshi_TouristFastest, 0.0s

Ahasan_1999Lightest, 524 kB

Alomgir27Shortest, 1286B

Submit

Login to submit