{"trustable":false,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cscript type\u003d\u0027text/x-mathjax-config\u0027\u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[\u0027$\u0027,\u0027$\u0027]] } }); \u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027 src\u003d\u0027https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\u0027\u003e\u003c/script\u003e\n\u003cscript type\u003d\u0027text/javascript\u0027\u003esetTimeout(function(){MathJax.Hub.Queue([\u0027Typeset\u0027, MathJax.Hub, \u0027left_view\u0027]);}, 2000);\u003c/script\u003e\n\u003cdiv class\u003d\"panel_content\"\u003e\n Pog and Szh are playing games. Firstly Pog draw a tree on the paper. Here we define 1 as the root of the tree.Then Szh choose some nodes from the tree. He wants Pog helps to find the least common ancestor (LCA) of these node.The question is too difficult for Pog.So he decided to simplify the problems.The nodes picked are consecutive numbers from $l_i$ to $r_i$ $([l_i, r_i])$. \n \u003cbr\u003e \n \u003cbr\u003eHint : You should be careful about stack overflow ! \n\u003c/div\u003e\n\u003cbr\u003e给定一个棵以1为根的n个节点的树,有Q个询问,每次询问节点编号在[L,R]范围的所有点的LCA"}},{"title":"Input","value":{"format":"HTML","content":"Several groups of data (no more than 3 groups,$n \\geq 10000$ or $Q \\geq 10000$). \n\u003cbr\u003e \n\u003cbr\u003eThe following line contains ans integers,$n (2 \\leq n \\leq 300000)$. \n\u003cbr\u003e \n\u003cbr\u003eAT The following $n-1$ line, two integers are $b_i$ and $c_i$ at every line, it shows an edge connecting $b_i$ and $c_i$. \n\u003cbr\u003e \n\u003cbr\u003eThe following line contains ans integers,$Q (Q \\leq 300000)$. \n\u003cbr\u003e \n\u003cbr\u003eAT The following $Q$ line contains two integers li and ri($1 \\leq li \\leq ri \\leq n$).\n\u003cbr\u003e多组输入数据,不超过3组。\n\u003cbr\u003e每组数组,第一行一个整数n,表示树上节点个数。\n\u003cbr\u003e接下来两个b和c,表示树上的一条边。\n\u003cbr\u003e接下来一个整数Q,表示询问次数。\n\u003cbr\u003e接下来Q行,每行两个整数,表示询问的节点编号区间。\n\u003cbr\u003en和Q,不超过300000。"}},{"title":"Output","value":{"format":"HTML","content":"For each case,output $Q$ integers means the LCA of $[l_i,r_i]$.\n\u003cbr\u003e对于每组数据,输出[L,R] 范围内,所有节点的LCA。"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre\u003e5\n1 2\n1 3\n3 4\n4 5\n5\n1 2\n2 3\n3 4\n3 5\n1 5\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre\u003e1\n1\n3\n3\n1\n\n\n\n \n \u003ci style\u003d\"font-size:1px\"\u003e \u003c/i\u003e\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cpre\u003eBe careful about stack overflow.\n \n \u003c/pre\u003e"}}]}