{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eThis is an interactive problem.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eAfter 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\u0027s now lost!\u003c/p\u003e\u003cp\u003eThe 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\u0027s hotel.\u003c/p\u003e\u003cp\u003eKuroni 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\u0027ll return a vertex $$$w$$$, which is the lowest common ancestor of those two vertices.\u003c/p\u003e\u003cp\u003eHowever, since the phone\u0027s battery has been almost drained out from live-streaming Kuroni\u0027s 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! :(\u003c/p\u003e\u003cp\u003eAs 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\u0027s location?\u003c/p\u003e"}},{"title":"Interaction","value":{"format":"HTML","content":"\u003cp\u003eThe interaction starts with reading a single integer $$$n$$$ ($$$2 \\le n \\le 1000$$$), the number of vertices of the tree.\u003c/p\u003e\u003cp\u003eThen you will read $$$n-1$$$ lines, the $$$i$$$-th of them has two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \\le x_i, y_i \\le n$$$, $$$x_i \\ne y_i$$$), denoting there is an edge connecting vertices $$$x_i$$$ and $$$y_i$$$. It is guaranteed that the edges will form a tree.\u003c/p\u003e\u003cp\u003eThen you can make queries of type \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e? u v\u003c/span\u003e\" ($$$1 \\le u, v \\le n$$$) to find the lowest common ancestor of vertex $$$u$$$ and $$$v$$$.\u003c/p\u003e\u003cp\u003eAfter the query, read the result $$$w$$$ as an integer.\u003c/p\u003e\u003cp\u003eIn case your query is invalid or you asked more than $$$\\lfloor \\frac{n}{2} \\rfloor$$$ queries, the program will print $$$-1$$$ and will finish interaction. You will receive a \u003cspan class\u003d\"tex-font-style-bf\"\u003eWrong answer\u003c/span\u003e verdict. Make sure to exit immediately to avoid getting other verdicts.\u003c/p\u003e\u003cp\u003eWhen you find out the vertex $$$r$$$, print \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e! $$$r$$$\u003c/span\u003e\" and quit after that. This query does not count towards the $$$\\lfloor \\frac{n}{2} \\rfloor$$$ limit.\u003c/p\u003e\u003cp\u003eNote that the tree is fixed beforehand and will not change during the queries, i.e. the interactor is not adaptive.\u003c/p\u003e\u003cp\u003eAfter printing any query do not forget to print end of line and flush the output. Otherwise, you might get \u003cspan class\u003d\"tex-font-style-tt\"\u003eIdleness limit exceeded\u003c/span\u003e. To do this, use:\u003c/p\u003e\u003cul\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003efflush(stdout)\u003c/span\u003e or \u003cspan class\u003d\"tex-font-style-tt\"\u003ecout.flush()\u003c/span\u003e in C++;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eSystem.out.flush()\u003c/span\u003e in Java;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003eflush(output)\u003c/span\u003e in Pascal;\u003c/li\u003e\u003cli\u003e \u003cspan class\u003d\"tex-font-style-tt\"\u003estdout.flush()\u003c/span\u003e in Python;\u003c/li\u003e\u003cli\u003e see the documentation for other languages.\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eHacks\u003c/span\u003e\u003c/p\u003e\u003cp\u003eTo hack, use the following format:\u003c/p\u003e\u003cp\u003eThe first line should contain two integers $$$n$$$ and $$$r$$$ ($$$2 \\le n \\le 1000$$$, $$$1 \\le r \\le n$$$), denoting the number of vertices and the vertex with Kuroni\u0027s hotel.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th of the next $$$n-1$$$ lines should contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \\le x_i, y_i \\le n$$$)\u0026nbsp;— denoting there is an edge connecting vertex $$$x_i$$$ and $$$y_i$$$.\u003c/p\u003e\u003cp\u003eThe edges presented should form a tree.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e6\n1 4\n4 2\n5 3\n6 3\n2 3\n\n3\n\n4\n\n4\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n\n\n\n\n\n? 5 6\n\n? 3 1\n\n? 1 2\n\n! 4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eNote that the example interaction contains extra empty lines so that it\u0027s easier to read. The real interaction doesn\u0027t contain any empty lines and you shouldn\u0027t print any extra empty lines as well.\u003c/p\u003e\u003cp\u003eThe image below demonstrates the tree in the sample test:\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/baf273ad12cad844091c0b22adcd2909?v\u003d1714647097\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e"}}]}