AT_past202112_k ガソリンスタンド

[problemUrl]: https://atcoder.jp/contests/past202112-open/tasks/past202112_k 高橋王国は $ 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 $ に行くとき、道を通る回数の最小値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 番目のクエリに対する答えを出力せよ。

### 制約 - $ 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\