JOI 王国是一个岛国，由 $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$ 名旅行者，他们计划参观 JOI 王国中的观光点。旅行者编号为 $1$ 到 $Q$。每位旅行者的行程方式如下：

1. 旅行者选择一个岛屿 $x$ ($1 \le x \le N$)。乘坐飞机到达岛屿 $x$。
2. 旅行者进行若干次以下操作。操作的顺序和种类是任意的：
   • 旅行者选择当前岛屿上的一个观光点并进行参观。
   • 旅行者通过一座桥梁移动到另一个岛屿。
3. 乘坐飞机，旅行者离开 JOI 王国。

第 $k$ 位旅行者 ($1 \le k \le Q$) 想要参观所有观光点 $L_k, L_k+1, \dots, R_k$。然而，由于预算有限，第 $k$ 位旅行者希望最小化其至少访问过一次的岛屿数量。

请编写一个程序，在给定 JOI 王国信息和旅行者信息的情况下，计算对于每位旅行者 $k$ ($1 \le k \le Q$)，其至少访问过一次的岛屿数量的最小值。

输入格式

从标准输入读取以下数据：

$N \ M \ Q$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_{N-1} \ B_{N-1}$ $C_1 \ C_2 \ \dots \ C_M$ $L_1 \ R_1$ $L_2 \ R_2$ $\vdots$ $L_Q \ R_Q$

输出格式

向标准输出写入 $Q$ 行。第 $k$ 行 ($1 \le k \le Q$) 应包含第 $k$ 位旅行者至少访问过一次的岛屿数量的最小值。

数据范围

• $1 \le N \le 100\,000$
• $1 \le M \le 100\,000$
• $1 \le Q \le 100\,000$
• $1 \le A_i \le N \ (1 \le i \le N-1)$
• $1 \le B_i \le N \ (1 \le i \le N-1)$
• 可以通过经过若干座桥梁从任意一个岛屿到达其他任何岛屿。
• $1 \le C_j \le N \ (1 \le j \le M)$
• $1 \le L_k \le R_k \le M \ (1 \le k \le Q)$
• 给定值均为整数。

子任务

1. (5 分) $N \le 300, M \le 300, Q \le 300$
2. (5 分) $N \le 2\,000, M \le 2\,000, Q \le 2\,000$
3. (7 分) $A_i = i, B_i = i+1 \ (1 \le i \le N-1)$
4. (18 分) $L_1 = 1, R_k + 1 = L_{k+1} \ (1 \le k \le Q-1), R_Q = M$
5. (24 分) $A_i = \lfloor \frac{i+1}{2} \rfloor, B_i = i+1 \ (1 \le i \le N-1)$。其中 $\lfloor x \rfloor$ 是不超过 $x$ 的最大整数。
6. (41 分) 无附加限制。

样例

样例输入 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

样例输出 1

4
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

样例输出 2

3
4
6
6
3
6
1
6
3

样例输入 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

样例输出 3

1
6
6
4
3
1
7
5
4