K - Gas Station Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

高橋王国は N 個の街と M 本の道路からなります。

街には 1,2,\ldots,N の番号がついており、i\,(1 \leq i \leq M) 本目の道路は街 u_i と街 v_i を双方向に結んでいます。どの街からどの街へもいくつかの道路をたどることで到達できることが保証されます。

また、街 a_1,a_2,\ldots,a_K にはガソリンスタンドがあります。

Q 個のクエリに答えてください。i\,(1 \leq i \leq Q) 番目のクエリは以下の内容です。

  • 街 s_i を出発し、ガソリンスタンドのある街を 1 つ以上通った後、街 t_i に行くとき、道を通る回数の最小値を求めよ。

制約

  • 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
  • 街 s_i,t_i にはガソリンスタンドがない
  • どの街からどの街へもいくつかの道路をたどることで到達できる
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力

Q 行出力せよ。i\,(1 \leq i \leq Q) 行目には、i 番目のクエリに対する答えを出力せよ。

入力例 1

3 2 1 1
1
1 2
2 3
3 2

出力例 1

3

街 3 を出発し、街 2、街 1、街 2 の順に移動すると移動回数は 3 回です。これより少ない移動回数は実現できないので 3 を出力します。

入力例 2

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

出力例 2

2
3

Score : 6 points

Problem Statement

The Kingdom of Takahashi has N towns and M roads.

The towns are numbered 1,2,\ldots,N, and the i-th road (1 \leq i \leq M) connects Town u_i and Town v_i bidirectionally. It is guaranteed that one can get from every town to every town by traversing some roads.

Additionally, there are gas stations in Towns a_1,a_2,\ldots,a_K.

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

  • Find the minimum number of times one needs to traverse a road when getting from Town s_i to Town t_i via a town with a gas station.

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
  • Nither s_i nor t_i has a gas station.
  • It is possible to get from every town to every town by traversing some roads.
  • All values in input are integers.

Input

Input is given from 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

Print Q lines. The i-th line (1 \leq i \leq Q) should contain the answer to the i-th query.

Sample Input 1

3 2 1 1
1
1 2
2 3
3 2

Sample Output 1

3

After starting in Town 3, we can go to Town 2, Town 1, Town 2 in this order to complete the trip with three moves. It is impossible to do it with fewer moves, so we print 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