题目描述
译自 JOISC 2023 Day3 T3 「旅行 / Tourism」

JOI 国是一个由 $N$ 个岛屿构成的岛国，这 $N$ 个岛屿编号为 $1$ 到 $N$。这些岛屿由 $N-1$ 座桥相连，这些桥编号为 $1$ 到 $N-1$。桥 $i$ $(1\le i\le N-1)$ 双向连接岛屿 $A_i$ 和 $B_i$。保证可以从一座岛屿出发，经过一定数量的桥到达任意其他岛屿。

在 JOI 国中，有 $M$ 个旅游景点，从 $1$ 到 $M$ 编号。景点 $j$ $(1\le j\le M)$ 位于岛屿 $C_j$ 上。

有 $Q$ 个旅行者，编号为 $1$ 到 $Q$。他们计划去 JOI 国旅游。每个旅行者按如下方式旅游：

• 旅行者选择一个岛屿 $x$ $(1\le x\le N)$，并乘飞机抵达岛屿 $x$
• 旅行者执行如下操作若干次，操作的顺序和种类任意
  • 旅行者选择目前岛上的一个景点并游览它
  • 旅行者通过一座桥移动到其他岛屿
• 旅行者乘飞机离开 JOI 国

旅行者 $k$ $(1\le k\le Q)$ 想要游览所有景点 $L_k, L_k+1, \ldots, R_k$。然而，由于预算有限，旅行者 $k$ 希望最小化至少去过一遍的岛屿数。

给定 JOI 国和旅行者的信息，写一个程序计算对于每个 $k$ $(1\le k\le Q)$，旅行者 $k$ 至少去过一遍的岛屿数的最小值。

---

输入格式
第一行三个整数 $N$, $M$, $Q$。

接下来 $N-1$ 行，每行两个整数 $A_i$, $B_i$。

接下来一行 $M$ 个整数 $C_1, C_2, \ldots, C_M$。

接下来 $Q$ 行，每行两个整数 $L_k$, $R_k$。

---

输出格式
输出 $Q$ 行，第 $k$ 行输出一个整数，表示旅行者 $k$ 至少去过一遍的岛屿数的最小值。

---

样例 1
输入

7 6 2
1 2
1 3
2 4
2 5
3 6
3 7
2 3 6 4 5 7
1 3
4 6

输出

4
6

旅行者 $1$ 按如下方式旅行，并游览景点 $1,2,3$：

• 旅行者 $1$ 到达岛屿 $2$
• 旅行者 $1$ 游览岛屿 $2$ 上的景点 $1$
• 旅行者 $1$ 从岛屿 $2$ 经过桥 $1$ 到达岛屿 $1$
• 旅行者 $1$ 从岛屿 $1$ 经过桥 $2$ 到达岛屿 $3$
• 旅行者 $1$ 游览岛屿 $3$ 上的景点 $2$
• 旅行者 $1$ 从岛屿 $3$ 经过桥 $5$ 到达岛屿 $6$
• 旅行者 $1$ 游览岛屿 $6$ 上的景点 $3$
• 旅行者 $1$ 从岛屿 $6$ 离开 JOI 国

旅行者 $1$ 至少到过一次的岛屿是岛屿 $1,2,3,6$。如果旅行者 $1$ 至少到过一次的岛屿数小于等于 $3$，就不可能游览所有景点 $1,2,3$ 了。因此第一行输出 $4$。

旅行者 $2$ 按如下方式旅行，并游览景点 $4,5,6$：

• 旅行者 $2$ 到达岛屿 $3$
• 旅行者 $2$ 从岛屿 $3$ 经过桥 $6$ 到达岛屿 $7$
• 旅行者 $2$ 游览岛屿 $7$ 上的景点 $6$
• 旅行者 $2$ 从岛屿 $7$ 经过桥 $6$ 到达岛屿 $3$
• 旅行者 $2$ 从岛屿 $3$ 经过桥 $2$ 到达岛屿 $1$
• 旅行者 $2$ 从岛屿 $1$ 经过桥 $1$ 到达岛屿 $2$
• 旅行者 $2$ 从岛屿 $2$ 经过桥 $3$ 到达岛屿 $4$
• 旅行者 $2$ 游览岛屿 $4$ 上的景点 $4$
• 旅行者 $2$ 从岛屿 $4$ 经过桥 $3$ 到达岛屿 $2$
• 旅行者 $2$ 从岛屿 $2$ 经过桥 $4$ 到达岛屿 $5$
• 旅行者 $2$ 游览岛屿 $5$ 上的景点 $5$
• 旅行者 $2$ 从岛屿 $5$ 离开 JOI 国

旅行者 $2$ 至少到过一次的岛屿是岛屿 $1,2,3,4,5,7$。如果旅行者 $2$ 至少到过一次的岛屿数小于等于 $5$，就不可能游览所有景点 $4,5,6$ 了。因此第二行输出 $6$。

这组样例满足子任务 $1,2,4,5,6$ 的限制。

---

样例 2
输入

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

输出

3
4
6
6
3
6
1
6
3

这组样例满足子任务 $1,2,3,6$ 的限制。

---

样例 3
输入

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

输出

1
6
6
4
3
1
7
5
4

这组样例满足子任务 $1,2,6$ 的限制。

---

数据范围与提示
对于所有输入数据，满足：

• $1\le N,M,Q\le 10^5$
• $1\le A_i,B_i\le N$
• 保证从一座岛屿出发，可以经过一定数量的桥到达任意其他岛屿
• $1\le C_j\le N$
• $1\le L_k\le R_k\le M$

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
1	$N,M,Q\le 300$	5
2	$N,M,Q\le 2\,000$
3	$A_i=i$, $B_i=i+1$	7
4	$L_1=1$, $R_k+1=L_{k+1}$, $R_Q=M$	18
5	$A_i=\lfloor\frac{i+1}{2}\rfloor$, $B_i=i+1$，这里 $\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数	24
6	无附加限制	41