{"raw_statement":[{"iden":"problem statement","content":"There is a tree with $N$ vertices, numbered $1, \\ldots, N$.  \nFor each pair of integers $u,v\\, (1 \\leq u,v \\leq N)$, the distance $d_{u,v}$ between Vertices $u, v$ is defined as the following.\n\n*   The number of edges contained in the shortest path connecting Vertices $u$ and $v$.\n\nYou are allowed to ask between $0$ and $2N$ questions (inclusive) in the following form.\n\n*   Ask the distance $d_{u,v}$ between Vertices $u,v$ for integers $u,v$ of your choice such that $1\\leq u,v \\leq N$ and $u+v>3$.\n\nFind the distance $d_{1,2}$ between Vertices $1,2$."},{"iden":"constraints","content":"*   $3 \\leq N \\leq 100$\n*   $N$ is an integer.\n*   The tree is determined before the start of the interaction between your program and the judge."},{"iden":"input and output","content":"**This is an interactive task**, in which your program and the judge interact via input and output.\nFirst, your program is given a positive integer $N$ from Standard Input:\n\n$N$\n\nThen, you get to ask questions.  \nA question should be printed in the following format (with a newline at the end):\n\n? $u$ $v$\n\nIf the question is valid, the response $d_{u,v}$ is given from Standard Input:\n\n$d_{u,v}$\n\nIf the question is judged invalid because, for example, it is malformed or you have asked too many questions, you get `-1` instead of the response:\n\n\\-1\n\nAt this point, your submission is already judged incorrect. The judge's program then terminates; yours should too, desirably.\nWhen you find the answer $d_{1,2}$, print it to Standard Output in the following format (with a newline at the end):\n\n! $d_{1,2}$"},{"iden":"notices","content":"*   **Flush Standard Output after each output. Otherwise, you might get the TLE verdict.**\n*   After printing the answer (or receiving `-1`), immediately terminate the program normally. Otherwise, the verdict would be indeterminate.\n*   The verdict for the case of a malformed output would be indeterminate.\n*   Specifically, note that too many newlines would also be seen as a malformed output."},{"iden":"sample input and output","content":"The following is a sample interaction for the tree shown in this image.\n![image](https://img.atcoder.jp/arc142/1435f0bc323a9e21cf3abf1c4911e826.png)\n\nInput\n\nOutput\n\nDescription\n\n`3`\n\nInteraction starts with the integer $N$.\n\n`?` `1` `3`\n\nAs the $1$\\-st question, you ask the distance between Vertices $1$ and $3$.\n\n`1`\n\nThe distance between Vertices $1,3$ is returned.\n\n`?` `2` `2`\n\nAs the $2$\\-nd question, you ask the distance between Vertices $2$ and $2$.\n\n`0`\n\nThe distance between Vertices $2,2$ is returned.\n\n`?` `2` `3`\n\nAs the $3$\\-rd question, you ask the distance between Vertices $2$ and $3$.\n\n`1`\n\nThe distance between Vertices $2,3$ is returned.\n\n`?` `3` `1`\n\nAs the $4$\\-th question, you ask the distance between Vertices $3$ and $1$.\n\n`1`\n\nThe distance between Vertices $3,1$ is returned.\n\n`?` `3` `2`\n\nAs the $5$\\-th question, you ask the distance between Vertices $3$ and $2$.\n\n`1`\n\nThe distance between Vertices $3,2$ is returned.\n\n`?` `2` `2`\n\nAs the $6$\\-th question, you ask the distance between Vertices $2$ and $2$.\n\n`0`\n\nThe distance between Vertices $2,2$ is returned.\n\n`!` `2`\n\nYou guess the distance between Vertices $1,2$ and terminate. The actual distance between them is $2$, so you would get the AC verdict."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}