小 A 想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。
开始，小 A 只有一棵结点数为 N 的树，结点的编号为 1,2,…,N，其中结点 1 为根；我们称这颗树为模板树。小 A 决定通过这棵模板树来构建一颗大树。构建过程如下：
（1）将模板树复制为初始的大树。
（2）以下(2.1)(2.2)(2.3)步循环执行 M 次
（2.1）选择两个数字 a,b，其中 1≤a≤N，1≤b≤当前大树的结点数。
（2.2）将模板树中以结点 a 为根的子树复制一遍，挂到大树中结点 b 的下方(也就是说，模板树中的结点 a 为根的子树复制到大树中后，将成为大树中结点 b 的子树)。
（2.3）将新加入大树的结点按照在模板树中编号的顺序重新编号。例如，假设在进行 2.2 步之前大树有 L 个结点，模板树中以 a 为根的子树共有 C 个结点，那么新加入模板树的 C 个结点在大树中的编号将是 L+1,L+2,…,L+C；大树中这 C 个结点编号的大小顺序和模板树中对应的 C个结点的大小顺序是一致的。
下面给出一个实例。假设模板树如下图：

根据第（1）步，初始的大树与模板树是相同的。在（2.1）步，假设选择了a=4，b=3.运行（2.2）和（2.3）后，得到新的大树如下图所示：

现在他想问你，树中一些结点对的距离是多少。

第一行三个整数：N,M,Q，以空格隔开，N 表示模板树结点数，M 表示第(2)中的循环操作的次数，Q 表示询问数量。
接下来 N-1 行，每行两个整数 fr,to，表示模板树中的一条树边。
再接下来 M 行，每行两个整数 x,to，表示将模板树中 x 为根的子树复制到大树中成为结点to 的子树的一次操作。
再接下来 Q 行，每行两个整数 fr,to，表示询问大树中结点 fr 和 to 之间的距离是多少。

输出 Q 行，每行一个整数，第 i 行是第 i 个询问的答案。

【样例解释】
经过两次操作后，大树变成了下图所示的形状：

结点 6 到 9 之间经过了 6 条边，所以距离为 6；类似地，结点 1 到 8 之间经过了 3 条边；结点 5 到 3 之间也经过了 3 条边。
【数据范围】
对于 30%的数据，N,M<=500；
对于 60%的数据，N<=3000；
对于 100%的数据，N,M,Q<=100000。

动态规划 最近公共祖先 LCA AHOI高中 2016 level7