3725. [模板]最近公共祖先

【题目描述】

给定一棵包含$n$个结点的有根树，设树的根为$1$，请你求出两个结点的最近公共祖先。

【输入格式】

第一行包含三个正整数 $n,m$，分别表示树的结点个数、询问的个数。

接下来 $n-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边。

接下来 $m$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

【输出格式】

输出包含 $m$ 行，每行包含一个正整数，依次为每一个询问的结果。

【样例输入】

5 5
1 2
1 3
2 4
2 5
4 3
3 2
4 5
4 4
2 5

【样例输出】

1
1
2
4
2

【数据范围与约定】

对于 $70\%$ 的数据，$N\leq 10000$，$M\leq 10000$。

对于 $100\%$ 的数据，$1 \leq N,M\leq 5\times10^5$，$1 \leq x, y,a ,b \leq N$。