{"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\u003eAfter the piece of a devilish mirror hit the Kay\u0027s eye, he is no longer interested in the beauty of the roses. Now he likes to watch snowflakes.\u003c/p\u003e\u003cp\u003eOnce upon a time, he found a huge snowflake that has a form of the tree (connected acyclic graph) consisting of \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e nodes. The root of tree has index \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e. Kay is very interested in the structure of this tree.\u003c/p\u003e\u003cp\u003eAfter doing some research he formed \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e queries he is interested in. The \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e-th query asks to find a centroid of the subtree of the node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e. Your goal is to answer all queries.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eSubtree\u003c/span\u003e of a node is a part of tree consisting of this node and all it\u0027s descendants (direct or not). In other words, subtree of node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e is formed by nodes \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e, such that node \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003c/span\u003e is present on the path from \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eu\u003c/i\u003e\u003c/span\u003e to root.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003eCentroid\u003c/span\u003e of a tree (or a subtree) is a node, such that if we erase it from the tree, the maximum size of the connected component will be at least two times smaller than the size of the initial tree (or a subtree).\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line of the input contains two integers \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 300 000\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003eq\u003c/i\u003e ≤ 300 000\u003c/span\u003e)\u0026nbsp;— the size of the initial tree and the number of queries respectively.\u003c/p\u003e\u003cp\u003eThe second line contains \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e, \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e3\u003c/sub\u003e, ..., \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e)\u0026nbsp;— the indices of the parents of the nodes from \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e to \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e. Node \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e is a root of the tree. It\u0027s guaranteed that \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ep\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e define a correct tree.\u003c/p\u003e\u003cp\u003eEach of the following \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eq\u003c/i\u003e\u003c/span\u003e lines contain a single integer \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ev\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/sub\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e)\u0026nbsp;— the index of the node, that define the subtree, for which we want to find a centroid.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each query print the index of a centroid of the corresponding subtree. If there are many suitable nodes, print any of them. It\u0027s guaranteed, that each subtree has at least one centroid.\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\u003e7 4\n1 1 3 3 5 3\n1\n2\n3\n5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n2\n3\n6\n\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":"\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/bd033391a497067e815b17e72a658f38?v\u003d1715425537\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"265px\"\u003e \u003c/center\u003e\u003cp\u003eThe first query asks for a centroid of the whole tree\u0026nbsp;— this is node \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e. If we delete node \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e the tree will split in four components, two of size \u003cspan class\u003d\"tex-span\"\u003e1\u003c/span\u003e and two of size \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe subtree of the second node consists of this node only, so the answer is \u003cspan class\u003d\"tex-span\"\u003e2\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eNode \u003cspan class\u003d\"tex-span\"\u003e3\u003c/span\u003e is centroid of its own subtree.\u003c/p\u003e\u003cp\u003eThe centroids of the subtree of the node \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e are nodes \u003cspan class\u003d\"tex-span\"\u003e5\u003c/span\u003e and \u003cspan class\u003d\"tex-span\"\u003e6\u003c/span\u003e\u0026nbsp;— both answers are considered correct.\u003c/p\u003e"}}]}