B Nation Travel

You are given a connected tree with n cities, numbered from 1 to n. The tree has n-1 undirected edges; each edge has a travel time of 1 unit. In addition, k of these cities have teleporters. The teleporter cities are given as \(b_1, b_2, \dots, b_k\). From any teleporter city, you may instantly (in 0 time) travel to any other teleporter city.

You will be given q queries. In the i^th query, you are given two cities \(u_i\) and \(v_i\). You need to determine the minimum time needed to travel from \(u_i\) to \(v_i\), where you can either travel along the tree edges (each costing 1 time unit) or use the teleporters (which cost 0 time to jump between teleporter cities). Note that if both cities have teleporters, you can teleport directly from one to the other.

The answer for each query is the minimum of:

• The tree distance between \(u_i\) and \(v_i\) (which can be computed as \(\text{depth}(u_i) + \text{depth}(v_i) - 2 \times \text{depth}(\text{LCA}(u_i, v_i))\)).
• The sum of the distance from \(u_i\) to its nearest teleporter and the distance from \(v_i\) to its nearest teleporter. In equation form, if \(d(x)\) denotes the distance from city \(x\) to the nearest teleporter, then the teleportation-assisted route takes \(d(u_i) + d(v_i)\) time units.

Your task is to compute this minimum time for each query.

Input Format: The first line contains three integers \(n, k, q\). The second line contains k distinct integers \(b_1, b_2, \cdots, b_k\) representing the teleporter cities. Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) representing an undirected edge between cities u and v. Each of the following q lines contains two integers \(u_i\) and \(v_i\) representing a query.

Output Format: For each query, output a single integer — the minimum time needed to travel from \(u_i\) to \(v_i\).

Note: Even if two teleporter cities are directly connected by an edge, you may choose to either walk along the edge or use the teleportation (which has 0 cost) if it provides a benefit.

inputFormat

The input begins with a line containing three space-separated integers n, k, and q representing the number of cities, the number of teleporter cities, and the number of queries respectively.

The next line contains k space-separated integers representing the teleporter cities.

The following n-1 lines each contain two integers u and v, indicating there is an undirected road connecting cities u and v.

Finally, the next q lines each contain two integers u_i and v_i representing the queries.

outputFormat

For each query, print a single line containing one integer — the minimum time needed to travel from the starting city to the destination city.

sample

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

2
2
0

</p>