小明的族谱 ### 题目描述 小明家的族谱很特别，族谱上一共有 $N$ 个人和 $N-1$ 个对应关系，每个人都有着自己的编号（$1\sim N$）。其中编号为 $1$ 的人是所有人的共同祖先。 这天，小明带着家里的族谱来到学校并将族谱里的关系一一整理了出来。 但粗心的他在回家的路上不小心将族谱给弄丢了。慌乱的他到处搜寻，终于在学校的失误招领处找到了他的族谱。 小明想要要回他的族谱，但失误招领出的工作人员无法确定小明就是族谱的主人，于是他从族谱中挑选了 $Q$ 对人，分别为 $(x_1,y_1),(x_2,y_2),...(x_Q,y_Q)$ 。对于每对人只要小明能迅速、正确的回答他们的最近公共祖先，他就把族谱还给小明。 然而此时的小明已经狼狈不堪了，慌乱的他根本无法思考...于是他把整理好的族谱关系交给了你，请你帮助他拿回族谱！ ### 输入描述 输入第一行包含两个正整数 $N,Q$，分别表示族谱上的人数和工作人员挑选的对数。 第 $2$ 到 $N$ 行每行包含两个正整数 $u,v$，表示 $u\leftrightarrow v$ 之间存在着对应关系。 第 $N+1$ 到 $N+Q$ 行每行包含两个正整数 $x,y$，表示工作人员挑选的一对人。 $2\leq N,Q \leq 5\times 10^5$，$1 \leq u_i, v_i\leq N$。 ### 输出描述 输出占 $Q$ 行，每行输出一个数，表示 $(x_i,y_i)$ 的最近公共祖先。 ### 输入输出样例 #### 示例 1 >输入 ```txt 3 1 1 2 1 3 2 3 ``` >输出 ```txt 1 ```