AT_past202005_m 行商計画問題

### 题目简述 给出一张 $n$ 点 $m$ 边的无向图，所有点互相可达。第 $i$ 条边连接点 $u_i$ 和点 $v_i$。每次使用一条边都会增加 $1$ 点代价。求出从点 $s$ 出发，至少访问 $t_1,t_2,...,t_k$ 这 $k$ 个点各一次的最小代价点数。最终不需要回到点 $s$。

第一行：$n,m$ 接下来 $m$ 行：第 $i$ 行为 $u_i,v_i$ 接下来一行：$s$ 接下来一行：$k$ 接下来一行：$t_1,t_2,...,t_k$

一个整数，最小代价点数。 ### 数据约束 - 输入均为整数； - $2 \le n \le 10^5$，$n-1 \le m \le 10^5$； - $1 \le u_i \lt v_i \le n$，且任意两对 $(u_i,v_i)$ 互不相同； - $1 \le s \le n$，$1 \le k \le \min(n-1,16)$； - $1 \le t_i \le n$，任意两对 $t_i$ 互不相同，$s$ 与任意一个 $t_i$ 都不同。

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