K - Gas Station

Contest Duration: 2021-12-11(Sat) 04:00 - 2021-12-11(Sat) 09:00 (local time) (300 minutes) Back to Home

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$ 番目のクエリに対する答えを出力せよ。

入力例 1Copy

Copy

出力例 1Copy

Copy

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

入力例 2Copy

Copy

出力例 2Copy

Copy

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 1Copy

Copy

Sample Output 1Copy

Copy

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 2Copy

Copy

Sample Output 2Copy

Copy

2
3