グラフの問題． ハミルトン閉路に近い． 大事な頂点が \(K \leq 17\) と少ない．
訪れた頂点を再び使う可能性はある． すべての大事な頂点を 1回以上使う． 訪れた頂点の集合と，最後に訪れた頂点を保持しながら dp. 大事な頂点間のコストは，BFS とWarshall-Floyd で求めておく．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, m;
cin >> n >> m;
vvll to(n);
rep(i,m){
ll a,b; cin >> a >> b;
--a, --b;
to[a].push_back(b);
to[b].push_back(a);
}
ll k; cin >> k;
vll c(k); cinv(c);
rep(i,k) c[i]--;
auto bfs = [&](ll src) -> vll {
vll dis(n, INFL);
queue<ll> que;
auto push = [&](ll v, ll d) -> void {
if(vis[v]) return;
vis[v] = true;
que.push(v);
dis[v] = d;
};
push(src, 0);
while(que.size()){
ll cu = que.front(); que.pop();
ll d = dis[cu];
for(auto ne: to[cu]){
push(ne, d + 1);
}
}
return dis;
};
vvll co(k, vll(k, INFL));
rep(i,k){
vll dis = bfs(c[i]);
rep(j,k){
co[i][j] = dis[c[j]]; // i 自身はカウントしない
}
}
rep(i, k) rep(cu,k) rep(ne,k){
chmin(co[cu][ne], co[cu][i] + co[i][ne]);
}
ll ans = INFL;
rep(i,k){
vvll dp(1LL<<k, vll(k, INFL));
dp[1LL << i][i] = 1; // ここで i自身をカウントする
rep(s, 1LL<<k) {
rep(cu, k) if(s >> cu & 1){
rep(ne, k){
ll ns = s | (1LL << ne);
chmin(dp[ns][ne], dp[s][cu] + co[cu][ne]);
}
}
}
rep(la, k){
chmin(ans, dp[(1LL<<k)-1][la]);
}
}
if(ans >= INFL) ans = -1;
cout << ans << endl;
return 0;
}
