题目描述

这是一道模板题。

给你一棵 $n$ 个点的有根树，以 $1$ 号点为根。给出 $q$ 个询问，每次询问树上两点的最近公共祖先。

输入格式

第一行两个正整数 $n,q$。
第二到 $n$ 行，每行两个正整数 $u,v$，表示一条连接 $u,v$ 两点的边。
第 $n+1$ 到 $n+q$ 行，每行两个正整数 $x,y$，表示询问点 $x,y$ 的最近公共祖先。

输出格式

共 $q$ 行，第 $i$ 行一个正整数 $ans$，表示第 $i$ 个询问的答案。

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

4
1
1
1

数据规模与约定

对于 $100\%$ 的数据，$n \leq 5 \times 10^5$，$q=\min(10^6,10^T)$。其中 $T$ 为测试点编号 ($T \in [0,10)$)