Thief and Uranium Heist

In this problem, you are a thief planning to steal some uranium to grow rapidly in the game Digdig.io. You are given an undirected graph representing a mine with (n) vertices and (m) edges. There are (K) guards protecting the mine; the (i)-th guard stands at vertex (P_i).

You steal (x) kilograms of uranium and intend to transfer it along a path from vertex (S) to vertex (T). If (x > 0), then during the transfer, at every vertex along your path, your distance (in terms of the number of edges) to each guard must be greater than (x) (i.e. for every vertex (u) on your path and for every guard, (d(u, P_i) > x) must hold) so that you are not caught. Note that if (x = 0), the safety condition is not enforced.

You will attempt to steal uranium (Q) times. In each attempt, you are given (S) and (T) and you are to determine the maximum amount of uranium (in kilograms) you can safely steal, i.e. the maximum (x) such that there exists an (S)-(T) path in which for every vertex (u) on the path, (d(u) > x), where (d(u) = \min_{i=1}^K\ d(u, P_i)).

Hint: You can precompute for every vertex its minimum distance to any guard via a multi-source BFS. Then, the problem reduces to finding an (S)-(T) path that maximizes the minimum clearance along the path. Finally, the answer for a query is (\max\big(\text{maximin}(S,T)-1,\ 0\big)). If no (S)-(T) path exists, output (-1).

inputFormat

The first line contains four integers \(n\), \(m\), \(K\), and \(Q\) — the number of vertices, edges, guards, and queries, respectively.

Then, \(m\) lines follow, each containing two integers \(u\) and \(v\) indicating that there is an undirected edge between vertices \(u\) and \(v\).

The next line contains \(K\) integers \(P_1, P_2, \dots, P_K\), where \(P_i\) is the vertex at which the \(i\)-th guard stands.

Each of the following \(Q\) lines contains two integers \(S\) and \(T\) representing a query.

outputFormat

For each query, output one integer representing the maximum number of kilograms of uranium that can be safely stolen. If there is no path from \(S\) to \(T\) (even when \(x = 0\)), output \(-1\).

sample

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

0