#include <bits/stdc++.h> using namespace std; #define ll long long #define v vector #define lp(i, s, e) for (ll i = s; i < e; ++i) ll n, m, k; v<v<ll>> g; string s; v<ll> x; bool stop(ll u) { return s[u] == '1'; } const ll inf = 1e18; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; g.resize(n + 1); lp(i, 0, m) { ll a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } cin >> s; s = " " + s; x.resize(k + 1); lp(i, 1, k + 1) cin >> x[i]; v<ll> sc; lp(i, 1, n + 1) if (stop(i)) sc.push_back(i); if (sc.empty()) { v<ll> d(n + 1, -1); queue<ll> q; d[x[1]] = 0; q.push(x[1]); while (!q.empty()) { ll u = q.front(); q.pop(); for (ll w : g[u]) if (d[w] == -1) { d[w] = d[u] + 1; q.push(w); } } lp(i, 1, n + 1) cout << d[i] << "\n"; return 0; } v<ll> ds(n + 1, inf); { queue<ll> q; for (ll u : sc) { ds[u] = 0; q.push(u); } while (!q.empty()) { ll u = q.front(); q.pop(); for (ll w : g[u]) if (ds[w] > ds[u] + 1) { ds[w] = ds[u] + 1; q.push(w); } } } v<ll> pc(n + 1, inf); lp(i, 1, n + 1) { ll mn = inf; for (ll u : g[i]) mn = min(mn, ds[u]); if (mn != inf) pc[i] = 1 + mn; } v<ll> ns(n + 1, -1); { for (ll u : sc) ns[u] = u; queue<ll> q; for (ll u : sc) q.push(u); while (!q.empty()) { ll u = q.front(); q.pop(); for (ll w : g[u]) if (ns[w] == -1) { ns[w] = ns[u]; q.push(w); } } } v<ll> ap(n + 1, -1); lp(i, 1, n + 1) { ll best = -1, mn = inf; for (ll u : g[i]) if (ds[u] < mn) { mn = ds[u]; best = u; } if (best != -1) ap[i] = ns[best]; } if (k == 2) { map<tuple<ll, ll, ll>, ll> d; priority_queue<tuple<ll, ll, ll, ll>, v<tuple<ll, ll, ll, ll>>, greater<>> pq; d[{x[1], x[2], 0}] = 0; pq.push({0, x[1], x[2], 0}); while (!pq.empty()) { auto [c, p1, p2, t] = pq.top(); pq.pop(); if (d[{p1, p2, t}] < c) continue; if (t == 0) { for (ll w : g[p1]) { ll nt = stop(w) ? 1 : 0; auto st = make_tuple(w, p2, nt); if (!d.count(st) || d[st] > c + 1) { d[st] = c + 1; pq.push({c + 1, w, p2, nt}); } } } else { for (ll w : g[p2]) { ll nt = stop(w) ? 0 : 1; auto st = make_tuple(p1, w, nt); if (!d.count(st) || d[st] > c + 1) { d[st] = c + 1; pq.push({c + 1, p1, w, nt}); } } } } lp(i, 1, n + 1) { ll ans = inf; for (auto [st, c] : d) if (get<0>(st) == i) ans = min(ans, c); cout << ans << "\n"; } return 0; } v<ll> pos(k + 1); lp(i, 2, k + 1) pos[i] = x[i]; const ll maxr = 300; v<ll> rc(maxr); lp(r, 0, maxr) { ll c = 0; lp(i, 2, k + 1) c += pc[pos[i]]; rc[r] = c; lp(i, 2, k + 1) pos[i] = ap[pos[i]]; } const ll inf = 1e18; v<v<array<ll, 2>>> dp(n + 1, v<array<ll, 2>>(maxr, {inf, inf})); priority_queue<tuple<ll, ll, ll, ll>, v<tuple<ll, ll, ll, ll>>, greater<>> pq; dp[x[1]][0][0] = 0; pq.push({0, x[1], 0, 0}); while (!pq.empty()) { auto [c, u, r, w] = pq.top(); pq.pop(); if (w == 0) { for (ll v : g[u]) { ll nw = stop(v) ? 1 : 0; if (c + 1 < dp[v][r][nw]) { dp[v][r][nw] = c + 1; pq.push({c + 1, v, r, nw}); } } } else { if (r < maxr - 1) { ll nc = c + rc[r]; if (nc < dp[u][r + 1][0]) { dp[u][r + 1][0] = nc; pq.push({nc, u, r + 1, 0}); } } } } lp(i, 1, n + 1) { ll ans = inf; lp(r, 0, maxr) { ans = min(ans, dp[i][r][0]); ans = min(ans, dp[i][r][1]); } cout << ans << '\n'; } return 0; }