{"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\"\u003e这是一个交互式问题。\u003c/span\u003e\u003c/p\u003e\u003cp\u003e在经历了13次超时的几何问题后,Kuroni前往意大利餐厅庆祝这一神圣的成就。不幸的是,多余的酱汁让他迷失了方向,他现在迷路了!\u003c/p\u003e\u003cp\u003e美利坚合众国可以被建模为一棵树(为什么呢),有$$$n$$$个顶点。这棵树以顶点$$$r$$$为根,Kuroni的酒店就在那里。\u003c/p\u003e\u003cp\u003eKuroni有一个手机应用程序,旨在帮助他在这种紧急情况下。要使用该应用程序,他必须输入两个顶点$$$u$$$和$$$v$$$,它将返回一个顶点$$$w$$$,即这两个顶点的最低公共祖先。\u003c/p\u003e\u003cp\u003e然而,由于手机的电池几乎被Kuroni庆祝派对的直播耗尽,他最多只能使用该应用程序$$$\\lfloor \\frac{n}{2} \\rfloor$$$次。之后,手机将会关机,我们的亲爱的朋友将无法得到任何帮助!:(\u003c/p\u003e\u003cp\u003e夜晚寒冷黑暗,Kuroni需要回去,这样他才能与他舒适的床和枕头团聚。你能帮助他找到他酒店的位置吗?\u003c/p\u003e"}},{"title":"交互","value":{"format":"HTML","content":"\u003cp\u003e交互从读取一个整数$$$n$$$($$$2 \\le n \\le 1000$$$)开始,表示树的顶点数。\u003c/p\u003e\u003cp\u003e然后,您将读取$$$n-1$$$行,其中第$$$i$$$行有两个整数$$$x_i$$$和$$$y_i$$$($$$1 \\le x_i, y_i \\le n$$$,$$$x_i \\ne y_i$$$),表示连接顶点$$$x_i$$$和$$$y_i$$$的边。保证这些边将形成一棵树。\u003c/p\u003e\u003cp\u003e然后,您可以进行类型为\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e? u v\u003c/span\u003e\"($$$1 \\le u, v \\le n$$$)的查询,以找到顶点$$$u$$$和$$$v$$$的最低公共祖先。\u003c/p\u003e\u003cp\u003e在查询后,将结果$$$w$$$作为整数读取。\u003c/p\u003e\u003cp\u003e如果您的查询无效或查询次数超过$$$\\lfloor \\frac{n}{2} \\rfloor$$$次,程序将打印$$$-1$$$并结束交互。您将收到一个\u003cspan class\u003d\"tex-font-style-bf\"\u003e错误答案\u003c/span\u003e的判决。请务必立即退出,以避免获得其他判决。\u003c/p\u003e\u003cp\u003e当您找到顶点$$$r$$$时,请打印\"\u003cspan class\u003d\"tex-font-style-tt\"\u003e! $$$r$$$\u003c/span\u003e\",然后退出。此查询不计入$$$\\lfloor \\frac{n}{2} \\rfloor$$$的限制。\u003c/p\u003e\u003cp\u003e请注意,树是事先固定的,在查询过程中不会改变,即交互器不是自适应的。\u003c/p\u003e\u003cp\u003e在打印任何查询后,不要忘记打印行尾并刷新输出。否则,您可能会收到\u003cspan class\u003d\"tex-font-style-tt\"\u003eIdleness limit exceeded\u003c/span\u003e。要做到这一点,请使用:\u003c/p\u003e\u003cul\u003e\u003cli\u003e 在C++中使用\u003cspan class\u003d\"tex-font-style-tt\"\u003efflush(stdout)\u003c/span\u003e或\u003cspan class\u003d\"tex-font-style-tt\"\u003ecout.flush()\u003c/span\u003e;\u003c/li\u003e\u003cli\u003e 在Java中使用\u003cspan class\u003d\"tex-font-style-tt\"\u003eSystem.out.flush()\u003c/span\u003e;\u003c/li\u003e\u003cli\u003e 在Pascal中使用\u003cspan class\u003d\"tex-font-style-tt\"\u003eflush(output)\u003c/span\u003e;\u003c/li\u003e\u003cli\u003e 在Python中使用\u003cspan class\u003d\"tex-font-style-tt\"\u003estdout.flush()\u003c/span\u003e;\u003c/li\u003e\u003cli\u003e 其他语言请参阅相应的文档。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003e黑客\u003c/span\u003e\u003c/p\u003e\u003cp\u003e要进行黑客,使用以下格式:\u003c/p\u003e\u003cp\u003e第一行应包含两个整数$$$n$$$和$$$r$$$($$$2 \\le n \\le 1000$$$,$$$1 \\le r \\le n$$$),表示顶点数和Kuroni酒店所在的顶点。\u003c/p\u003e\u003cp\u003e接下来的$$$n-1$$$行中的第$$$i$$$行应包含两个整数$$$x_i$$$和$$$y_i$$$($$$1 \\le x_i, y_i \\le n$$$)— 表示连接顶点$$$x_i$$$和$$$y_i$$$的边。\u003c/p\u003e\u003cp\u003e所呈现的边应形成一棵树。\u003c/p\u003e"}},{"title":"示例1","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"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e请注意,示例交互包含额外的空行,以便更容易阅读。实际交互不包含任何空行,您也不应打印任何额外的空行。\u003c/p\u003e\u003cp\u003e下面的图片展示了示例测试中树的结构:\u003c/p\u003e\u003cp\u003e\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/baf273ad12cad844091c0b22adcd2909?v\u003d1710849861\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u003c/p\u003e"}}]}