AT_past202005_m 行商計画問題

[problemUrl]: https://atcoder.jp/contests/past202005-open/tasks/past202005_m スーヌケ王国には $ N $ 個の街があります。 王国には $ M $ 本の道が存在していて、$ i $ 番目の道は、街 $ u_i $, $ v_i $ を双方向に繋いでいます。 ある道を $ 1 $ 回利用するためには、通行料として $ 1 $ 円を払う必要があります。 任意の街から出発して、いくつかの道を経由することで任意の街に辿り着けることが分かっています。 王国の行商人であるタカーハ氏は現在街 $ s $ にいて、これから $ K $ 個の街 $ t_1,\ t_2,\ \ldots,\ t_K $ で取引をしたいと思っています。 街 $ s $ から出発して $ K $ 個の街それぞれを少なくとも $ 1 $ 回は訪れるために、タカーハ氏が払う必要のある通行料の合計は最小で何円でしょうか。 最終的に街 $ s $ に戻ってくる必要はありません。 同じ道を複数回利用するとき、その都度通行料を払う必要があることに注意してください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ u_1 $ $ v_1 $ $ u_2 $ $ v_2 $ $ \vdots $ $ u_M $ $ v_M $ $ s $ $ K $ $ t_1 $ $ t_2 $ $ \ldots $ $ t_K $

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

### 注意 この問題に対する言及は、2020/6/6 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。 ### 制約 - 入力は全て整数である。 - $ 2\ \leq\ N\ \leq\ 10^5 $ - $ N\ -\ 1\ \leq\ M\ \leq\ 10^5 $ - $ 1\ \leq\ u_i\