背景

GESP八级样题

描述

小杨准备前往 B 国旅游。

B 国有 $n$ 座城市，这 $n$ 座城市依次以 $1$ 至 $n$ 编号。城市之间由 $n-1$ 条双向道路连接，任意两座城市之间均可达（即任意两座城市之间存在可达的路径）。

小杨可以通过双向道路在城市之间移动，通过一条双向道路需要 $1$ 单位时间。

B 国城市中有 $k$ 座城市设有传送门。设有传送门的城市的编号依次为 $b_1, b_2, ... , b_k$ 。小杨可以从任意一座设有传送门的城市花费 $0$ 单位时间前往另一座设有传送门的城市。

注：如果两座设有传送门的城市之间存在双向道路，那么小杨可以选择通过双向道路移动，也可以选择通过传送门传送。

小杨计划在 B 国旅游 $q$ 次。第 $i$ 次旅游（ $1 ≤ i ≤ q$），小杨计划从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市，小杨希望你能求出所需要的最短时间。

格式

输入

第一行包含三个正整数 $n, k, q$ ，分别表示 B 国的城市数量，设有传送门的城市数量，以及小杨计划在 B 国旅游的次数。

接下来 $n-1$ 行，每行包含两个正整数 $x_i, y_i$，表示一条双向道路连接的两座城市的编号。

第 $n + 1$ 行包含 $k$ 个正整数 $b_1, b_2, ... , b_k$，表示设有传送门的城市的编号。

接下来 $q$ 行，每行包含两个正整数 $u_i, v_i$ ，表示小杨第 $i$ 次旅游行程的起点城市编号与终点城市编号。

输出

输出共 $q$ 行。第 $i$ 行（ $1 ≤ i ≤ q$ ）输出一个非负整数，表示小杨计划第 $i$ 次旅游从编号为 $u_i$ 的城市前往编号为 $v_i$ 的城市所需要的最短时间。

样例

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

4

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

2 
1 
4

子任务

对于全部数据，保证有$ 1 ≤ k ≤ n ≤ 2 \times 10 ^ 5， 1 ≤ q ≤ 2 \times 10^5， 1 ≤ x_i, y_i ≤ n, 1 ≤ u_i, v_i ≤ n$。对于所有$1 ≤ i ≤ n - 1$, 有$x_i \neq y_i$。

限制

时间限制：1.0s 内存限制：128.0MB