题目描述

Byteburg 由历史城区和新城区组成。

历史城区是一棵由 $n$ 个广场和 $n-1$ 条大道构成的树。广场编号为 $1,2,\ldots,n$，主广场 $1$ 是这棵树的根。

最初，整座城市只有历史城区。之后每一年，城市按照如下方式扩张。设这一年开始时城市中共有 $m$ 个广场：

1. 在历史城区中选择一个广场 $f$，再在当前已经建成的所有广场中选择一个广场 $t$（$t$ 可以位于历史城区，也可以位于新城区）。
2. 将历史城区中以 $f$ 为根的整棵子树 $T$ 完整复制到新城区，并用一条大道把复制出来的子树根与广场 $t$ 相连。所有新建广场和大道均属于新城区，历史城区本身始终不发生变化。
3. 设子树 $T$ 中共有 $k$ 个广场。新复制出的广场依次获得编号 $m+1,m+2,\ldots,m+k$。编号顺序保持原子树中的编号大小关系：如果 $T$ 中原广场 $i<j$，那么它们对应的复制广场 $i',j'$ 也满足 $i'<j'$。

给定历史城区的树形结构，以及连续 $y$ 年的城市扩张过程。你需要回答若干询问：求最终城市中两个给定广场之间的最短距离。

输入格式

第一行包含三个整数 $n,y,q$，分别表示历史城区中的广场数、扩张年份数和询问数。

接下来 $n-1$ 行，每行两个整数 $a,b$，表示历史城区中广场 $a$ 与 $b$ 之间有一条大道：

保证这些边构成一棵树，根为编号 $1$ 的主广场。

接下来 $y$ 行，每行两个整数 $f,t$，描述对应年份的扩张操作：

• $1\le f\le n$；
• $t\ge 1$；
• $t$ 不超过该年开始时城市中已有的广场总数。

接下来 $q$ 行，每行两个整数 $i,j$，询问广场 $i$ 与广场 $j$ 之间的距离。

设经过 $y$ 年扩张后城市中共有 $M$ 个广场，则保证：

注意：$M$ 可能远大于 $10^5$，甚至无法显式建立最终整棵树。

输出格式

对于每个询问，输出一个整数，表示对应两个广场之间的最短距离。

样例

5 2 4
1 3
1 4
3 2
3 5
3 4
4 2
5 9
1 8
6 3
4 7

3
3
4
1