M - 行商計画問題 解説 /

実行時間制限: 2.5 sec / メモリ制限: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

スーヌケ王国には N 個の街があります。

王国には M 本の道が存在していて、i 番目の道は、街 u_i, v_i を双方向に繋いでいます。 ある道を 1 回利用するためには、通行料として 1 円を払う必要があります。 任意の街から出発して、いくつかの道を経由することで任意の街に辿り着けることが分かっています。

王国の行商人であるタカーハ氏は現在街 s にいて、これから K 個の街 t_1, t_2, \ldots, t_K で取引をしたいと思っています。

街 s から出発して K 個の街それぞれを少なくとも 1 回は訪れるために、タカーハ氏が払う必要のある通行料の合計は最小で何円でしょうか。 最終的に街 s に戻ってくる必要はありません。

同じ道を複数回利用するとき、その都度通行料を払う必要があることに注意してください。

制約

  • 入力は全て整数である。
  • 2 \leq N \leq 10^5
  • N - 1 \leq M \leq 10^5
  • 1 \leq u_i < v_i \leq N
  • i \neq j のとき (u_i, v_i) \neq (u_j, v_j)
  • 1 \leq s \leq N
  • 1 \leq K \leq \min (N - 1, 16)
  • 1 \leq t_i \leq N
  • i \neq j のとき t_i \neq t_j
  • s \neq t_i

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
s
K
t_1 t_2 \ldots t_K

出力

タカーハ氏が払う必要のある通行料の合計の最小値を整数として出力せよ。

入力例 1

3 2
1 2
2 3
2
2
1 3

出力例 1

3

まず街 2 から街 1 に移動して、その後再び街 2 へと戻り、次に街 3 へと移動することで、 合計 3 円の通行料で街 1 と街 3 を訪れることができます。

入力例 2

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

出力例 2

4

Score : 6 points

Warning

Do not make any mention of this problem until June 6, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

The Kingdom of Soonuke has N towns.

There are M roads in the kingdom. The i-th road connects Town u_i and v_i bidirectionally. You need to pay the toll of 1 yen each time you use a road. We know that any town can be reached from any town by using some number of roads.

Takaaha, a merchant, is now at Town s and wants to make transactions in K towns t_1, t_2, \ldots, t_K

What is the minimum total toll Takaaha needs to pay when he starts at Town s and visit each of the K towns at least once? He does not need to come back to Town s in the end.

Note that using the same road multiple times will cost you the toll that number of times.

Constraints

  • All values in input are integers.
  • 2 \leq N \leq 10^5
  • N - 1 \leq M \leq 10^5
  • 1 \leq u_i < v_i \leq N
  • If i \neq j, (u_i, v_i) \neq (u_j, v_j).
  • 1 \leq s \leq N
  • 1 \leq K \leq \min (N - 1, 16)
  • 1 \leq t_i \leq N
  • If i \neq j, t_i \neq t_j.
  • s \neq t_i

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
s
K
t_1 t_2 \ldots t_K

Output

Print the minimum total toll Takaaha needs to pay, as an integer.

Sample Input 1

3 2
1 2
2 3
2
2
1 3

Sample Output 1

3

If we go from Town 2 to Town 1, then go back to Town 2, then go to Town 3, we can visit the towns 1 and 3 with the total toll of 3 yen.

Sample Input 2

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

Sample Output 2

4