{"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\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"epigraph\"\u003e\u003cdiv class\u003d\"epigraph-text\"\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eThe real is the rational, and the rational is the real.\u003c/span\u003e\u003c/div\u003e\u003cdiv class\u003d\"epigraph-source\"\u003e— G.W.F.Hegel, \u003cspan class\u003d\"tex-font-style-it\"\u003eGrundliniender Philosophiedes Rechts\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eThis is an interactive problem.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eOne day, you wake up to find \u003cspan class\u003d\"tex-font-style-it\"\u003eMiku\u003c/span\u003e in front of you. Instead of singing, she wants to play a game with you!\u003c/p\u003e\u003cp\u003eThis game is played on a tree with $$$n$$$ nodes, which is rooted at node $$$1$$$. A tree is a connected graph without cycles.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eMiku\u003c/span\u003e has hidden a \u003cspan class\u003d\"tex-font-style-it\"\u003efufu\u003c/span\u003e at node $$$x$$$. You need to ask \u003cspan class\u003d\"tex-font-style-it\"\u003eMiku\u003c/span\u003e the following two types of queries to find the location of it:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1~u$$$ $$$(1 \\le u \\le n)$$$. \u003cspan class\u003d\"tex-font-style-it\"\u003eMiku\u003c/span\u003e will tell you the distance between node $$$u$$$ and node $$$x$$$. Here, the distance between two nodes denotes the number of edges in the shortest path between them. \u003c/li\u003e\u003cli\u003e $$$2~v$$$ $$$(1 \\le v \\le n)$$$. \u003cspan class\u003d\"tex-font-style-it\"\u003eMiku\u003c/span\u003e will tell you the second node on the shortest path from node $$$v$$$ to node $$$x$$$. However, when executing this query, you need to ensure that \u003cspan class\u003d\"tex-font-style-bf\"\u003e$$$v$$$ is an ancestor of $$$x$$$\u003c/span\u003e$$$^{\\dagger}$$$, or you will immediately receive a \u003cspan class\u003d\"tex-font-style-tt\"\u003eWrong Answer\u003c/span\u003e verdict due to \u003cspan class\u003d\"tex-font-style-it\"\u003eMiku\u0027s\u003c/span\u003e unhappiness. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003e$$$^{\\dagger}$$$ Node $$$a$$$ is an ancestor of node $$$b$$$ if and only if $$$a\\neq b$$$, and the shortest path from node $$$1$$$ to node $$$b$$$ passes through $$$a$$$. Note that in this problem, node $$$a$$$ is \u003cspan class\u003d\"tex-font-style-bf\"\u003enot an ancestor of $$$a$$$ itself.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eCan you find $$$x$$$ within $$$39$$$ queries? If you do, \u003cspan class\u003d\"tex-font-style-it\"\u003eMiku\u003c/span\u003e will give you a \u003cspan class\u003d\"tex-font-style-it\"\u003efufu\u003c/span\u003e as a reward!\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$n$$$ $$$(2 \\le n \\le 3.9 \\times 10^5)$$$, denoting the number of nodes in the tree.\u003c/p\u003e\u003cp\u003eThe $$$i$$$-th of the next $$$n-1$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \\le u_i, v_i \\le n$$$), denoting the $$$i$$$-th edge on the tree. \u003c/p\u003e\u003cp\u003eIt is guaranteed that the input edges form a tree.\u003c/p\u003e"}},{"title":"Interaction","value":{"format":"HTML","content":"\u003cp\u003eTo make a query, you can output one of the following two formats:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$1~u$$$ ($$$1 \\le u \\le n$$$), or \u003c/li\u003e\u003cli\u003e $$$2~v$$$ ($$$1 \\le v \\le n$$$). \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eAfter making a query, you should read the corresponding response, which represents the distance from $$$u$$$ to $$$x$$$ or the second node on the path from $$$v$$$ to $$$x$$$, depending on your query.\u003c/p\u003e\u003cp\u003eIf the response you read is $$$-1$$$, it means that you may have exceeded the number of allowed queries, made an invalid query, or violated the restriction for the second type of query. In this case, you should immediately exit the program and receive a \u003cspan class\u003d\"tex-font-style-tt\"\u003eWrong Answer\u003c/span\u003e verdict; otherwise, you may receive \u003cspan class\u003d\"tex-font-style-bf\"\u003ea random verdict\u003c/span\u003e other than Accepted.\u003c/p\u003e\u003cp\u003eAfter printing a query, do not forget to output end of line and flush the output. Otherwise, you will get \u003cspan class\u003d\"tex-font-style-tt\"\u003eRuntime Error\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\"\u003estdout.flush()\u003c/span\u003e in Python. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eTo print the answer, please output \u003cspan class\u003d\"tex-font-style-tt\"\u003e\"! x\"\u003c/span\u003e (Without quotes). Note that giving this answer is not counted towards the limit of $$$39$$$ queries.\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\u003e5\n1 2\n1 3\n3 4\n3 5\n\n3\n\n4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e\n\n\n\n\n1 2\n\n2 3\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\u003eIn the example, the hidden \u003cspan class\u003d\"tex-font-style-it\"\u003efufu\u003c/span\u003e is at node $$$x \u003d 4$$$.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/c181079f79d541ec2ce3868c1fd11b7b?v\u003d1726273189\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"270px\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003eThe tree in the example\u003c/span\u003e \u003c/center\u003e\u003cp\u003eYou can make the following queries:\u003c/p\u003e\u003col\u003e \u003cli\u003e Ask the distance between node $$$2$$$ and $$$x$$$, and get the reply $$$3$$$. It can be inferred that $$$x \u003d 4$$$ or $$$5$$$; \u003c/li\u003e\u003cli\u003e Ask the second node from node $$$3$$$ to $$$x$$$, and get the reply $$$4$$$. Note that node $$$3$$$ is the parent node of node $$$x$$$, so the second node is node $$$x$$$. Therefore, $$$x \u003d 4$$$; \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eOutput the answer $$$4$$$, and you can get the reward.\u003c/p\u003e\u003cp\u003eNote that this is \u003cspan class\u003d\"tex-font-style-bf\"\u003enot\u003c/span\u003e the only way to get the answer.\u003c/p\u003e"}}]}