#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) #define pll pair<ll, ll> const ll inf = 1e18; ll n, m, k; v<v<ll>> g; string str; v<ll> type, dist1, dist2, c, csum, ans, dist; v<bool> chk; struct state { ll idx, cnt, val, jump; bool operator<(const state &b) const { return val - csum[cnt] > b.val - csum[b.cnt]; } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> k; g.resize(n + 1); type.resize(n + 2, 0); dist1.resize(n + 2, inf); dist2.resize(n + 2, inf); c.resize(n + 2, 0); csum.resize(n + 2, 0); ans.resize(n + 2, inf); dist.resize(n + 2, inf); chk.resize(n + 2, false); lp(i, 0, m) { ll a, b; cin >> a >> b; g[a].push_back(b); g[b].push_back(a); } ll s; cin >> str >> s; str = "0" + str; lp(i, 1, n + 1) { if (str[i] == '1') { bool f = false; for (ll nx : g[i]) f |= (str[nx] == '1'); type[i] = f ? 2 : 1; } } queue<tuple<ll, ll, ll>> qq; lp(i, 1, n + 1) { if (type[i] == 1) { chk[i] = true; qq.push({i, i, 0}); } } while (!qq.empty()) { auto [idx, frm, val] = qq.front(); qq.pop(); dist1[idx] = val; for (ll nx : g[idx]) { if (!chk[nx]) { chk[nx] = true; qq.push({nx, frm, val + 1}); } } } deque<ll> dq; lp(i, 1, n + 1) { if (type[i] == 2) { dq.push_back(i); dist2[i] = 0; } } while (!dq.empty()) { ll cur = dq.front(); dq.pop_front(); for (ll nx : g[cur]) { if (type[cur] != 1) { if (dist2[nx] > dist2[cur] + 1) { dist2[nx] = dist2[cur] + 1; dq.push_back(nx); } } else { if (dist2[nx] > dist2[cur]) { dist2[nx] = dist2[cur]; dq.push_front(nx); } } } } lp(i, 0, k - 1) { ll x; cin >> x; if (dist2[x] >= inf) { if (!type[x]) { c[1] += dist1[x]; c[2] += -dist1[x] + 2; } else { c[1] += 2; } } else if (dist1[x] >= inf) { if (!type[x]) { c[1] += dist2[x]; c[2] += -dist2[x] + 1; } else { c[1] += 1; } } else if (!type[x]) { if (dist1[x] >= dist2[x]) { c[1] += dist2[x]; c[2] += -dist2[x] + 1; } else { c[1] += dist1[x]; c[2] += -dist1[x] + 2; c[min(n + 1, 2 + dist2[x] - dist1[x])] -= 1; } } else if (type[x] == 1) { c[1] += 2; c[dist2[x]] -= 1; } else { c[1] += 1; } } ll add = 0; lp(i, 1, n + 1) { add += c[i]; c[i] = add; csum[i] = csum[i - 1] + c[i]; ans[i] = inf; dist[i] = inf; } priority_queue<state> pq; pq.push({s, 0, 0, 0}); dist[s] = 0; while (!pq.empty()) { auto [idx, cnt, val, jump] = pq.top(); pq.pop(); if (cnt > n) continue; ans[idx] = min(ans[idx], val); if (jump) { if (dist[idx] < inf && val > dist[idx]) continue; pq.push({idx, cnt, val + c[cnt], 0}); continue; } for (ll nx : g[idx]) { if (dist[nx] < inf && val + 1 >= dist[nx]) continue; dist[nx] = min(dist[nx], val + 1); if (type[nx]) pq.push({nx, cnt + 1, val + 1, 1}); else pq.push({nx, cnt, val + 1, 0}); } } lp(i, 1, n + 1) cout << ans[i] << '\n'; return 0; }