{"trustable":true,"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":"\u003cdiv class\u003d\"panel_content\"\u003ePog 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])$.\u003cbr\u003e\u003cbr\u003eHint : You should be careful about stack overflow !\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Several groups of data (no more than 3 groups,$n \\geq 10000$ or $Q \\geq 10000$).\u003cbr\u003e\u003cbr\u003eThe following line contains ans integers,$n (2 \\leq n \\leq 300000)$.\u003cbr\u003e\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$. \u003cbr\u003e\u003cbr\u003eThe following line contains ans integers,$Q (Q \\leq 300000)$.\u003cbr\u003e\u003cbr\u003eAT The following $Q$ line contains two integers li and ri($1 \\leq li \\leq ri \\leq n$)."}},{"title":"Output","value":{"format":"HTML","content":"For each case,output $Q$ integers means the LCA of $[l_i,r_i]$."}},{"title":"Sample","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\r\n1 2\r\n1 3\r\n3 4\r\n4 5\r\n5\r\n1 2\r\n2 3\r\n3 4\r\n3 5\r\n1 5\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n1\r\n3\r\n3\r\n1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"Be careful about stack overflow."}}]}