题目描述
Problem Description
Xiao Yang is preparing to travel to Country B.
Country B has $n$ cities, numbered sequentially from $1$ to $n$. These cities are connected by $n-1$ bidirectional roads, ensuring that any two cities are reachable from each other.
Xiao Yang can move between cities using the bidirectional roads, which take $1$ unit of time to traverse.
There are $k$ cities in Country B that have teleportation gates. The numbers of these cities are $b_1, b_2, \cdots, b_k$. Xiao Yang can travel from any city with a teleportation gate to another city with a teleportation gate in $0$ units of time.
Note: If there is a bidirectional road between two cities with teleportation gates, Xiao Yang can choose to travel by road or use the teleportation gate.
Xiao Yang plans to travel in Country B $q$ times. For the $i$-th trip ($1 \leq i \leq q$), Xiao Yang plans to travel from city $u_i$ to city $v_i$, and he hopes you can calculate the shortest time required.
Input Format
The first line contains three positive integers $n, k, q$, representing the number of cities in Country B, the number of cities with teleportation gates, and the number of trips Xiao Yang plans to make, respectively.
The next $n-1$ lines each contain two positive integers $x_i, y_i$, indicating the numbers of the two cities connected by a bidirectional road.
The $n+1$-th line contains $k$ positive integers, representing the numbers of the cities with teleportation gates.
The next $q$ lines each contain two positive integers $u_i, v_i$, indicating the starting and ending city numbers for Xiao Yang's $i$-th trip.
Output Format
Output $q$ lines. The $i$-th line ($1 \leq i \leq q$) should output a non-negative integer, representing the shortest time required for Xiao Yang's $i$-th trip from city $u_i$ to city $v_i$.
Sample Input and Output
Input Sample #1
7 2 1
5 7
3 6
2 3
1 5
5 4
1 2
7 4
3 7
Output Sample #1
4
Input Sample #2
5 0 3
2 3
5 1
5 2
1 4
4 5
4 5
1 4
4 3
Output Sample #2
2
1
4
Notes
| Subtask | Score | $n \leq$ | $k \leq$ | $q \leq$ |
|---|---|---|---|---|
| $1$ | $30$ | $500$ | $500$ | $1$ |
| $2$ | $30$ | $2 \times 10^5$ | $0$ | $2 \times 10^5$ |
| $3$ | $40$ | $2 \times 10^5$ | $2 \times 10^5$ | $2 \times 10^5$ |
For all test data, $1 \leq n \leq 2 \times 10^5$, $0 \leq k \leq n$, $1 \leq x_i, y_i, u_i, v_i \leq n$, $x_i \neq v_i$.
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分