Problem Description

The Takahashi Kingdom consists of $ N $ cities and $ M $ roads.

The cities are numbered $1, 2, \ldots, N$, and the $ i $th road ($1 \leq i \leq M$) connects city $ u_i $ and city $ v_i $ bidirectionally. It is guaranteed that any city can be reached from any other city by traversing some roads.

Additionally, cities $a_1, a_2, \ldots, a_K$ have gas stations.

Answer $ Q $ queries. The $ i $th query ($1 \leq i \leq Q$) is as follows:

• Starting from city $ s_i $, find the minimum number of road traversals to reach city $ t_i $ after passing through at least one city with a gas station.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ Q $ $ K $ $ a_1 $ $ a_2 $ $\ldots$ $ a_K $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $\vdots$ $ u_M $ $ v_M $ $ s_1 $ $ t_1 $ $ s_2 $ $ t_2 $ $\vdots$ $ s_Q $ $ t_Q $

Output Format

Output $ Q $ lines. The $ i $th line should contain the answer to the $ i $th query.

Sample Input and Output

Sample Input #1

3 2 1 1
1
1 2
2 3
3 2

Sample Output #1

3

Sample Input #2

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

Sample Output #2

2
3

Notes/Hints

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq M, Q \leq 2 \times 10^5$
• $1 \leq K \leq \min(N-1, 20)$
• $1 \leq a_i \leq N$
• $a_i \neq a_j$ ($i \neq j$)
• $1 \leq u_i < v_i \leq N$
• $(u_i, v_i) \neq (u_j, v_j)$ ($i \neq j$)
• $1 \leq s_i, t_i \leq N$
• Cities $ s_i, t_i $ do not have gas stations
• Any city can be reached from any other city by traversing some roads
• All inputs are integers

Sample Explanation 1

Starting from city $ 3 $, moving through cities $ 2 $, $ 1 $, and then $ 2 $ again results in 3 moves. This is the minimum number of moves that cannot be reduced further, so output 3.

见题面 Input 部分

见题面 Output 部分