小明的族谱

题目描述

小明家的族谱很特别，族谱上一共有 $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

>输入

3 1
1 2 
1 3
2 3

>输出

1