#ifndef LOCAL #pragma GCC Optimize("O3,Ofast,unroll-loops") #pragma GCC Target("bmi,bmi2,avx,avx2") #endif #include <bits/stdc++.h> using namespace std; using ll = long long; using ld = long double; #define int ll #define f first #define s second #define mp make_pair #define pb push_back #define pii pair<int, int> #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin() (x).rend() #ifndef LOCAL #define endl "\n" #endif mt19937 rnd(11); void solve() { int n, m, k; cin >> n >> m >> k; vector<vector<int>> graph(n); for (int i = 0; i < m; ++i) { int a, b; cin >> a >> b; --a; --b; graph[a].pb(b); graph[b].pb(a); } string s; cin >> s; vector<int> p(k); for (auto &x : p) { cin >> x; --x; } int st = p[0]; p.erase(p.begin()); --k; vector<int> dist1(n, 1e9); vector<int> dist2(n, 1e9); vector<int> rd1(n, 1e9); vector<int> marked(n); priority_queue<pii> q; for (int i = 0; i < n; ++i) { if (s[i] == '1') { q.push(mp(0, i)); dist1[i] = 0; } } while (!q.empty()) { int v = q.top().s; q.pop(); if (marked[v]) { continue; } marked[v] = true; for (auto &u : graph[v]) { if (dist1[u] > dist1[v] + 1) { dist1[u] = dist1[v] + 1; q.push(mp(-dist1[u], u)); } } } for (int i = 0; i < n; ++i) { if (s[i] == '1') { bool ok = false; for (auto &u : graph[i]) { if (s[u] == '1') { rd1[i] = 1; ok = true; break; } } if (!ok) { rd1[i] = 2; } } else { rd1[i] = dist1[i]; } } marked.assign(n, false); for (int i = 0; i < n; ++i) { if (s[i] == '1') { bool ok = false; for (auto &u : graph[i]) { if (s[u] == '1') { ok = true; break; } } if (ok) { dist2[i] = 0; q.push(mp(-0, i)); } } } while (!q.empty()) { int v = q.top().s; q.pop(); if (marked[v]) { continue; } marked[v] = true; for (auto &u : graph[v]) { if (dist2[u] > dist2[v] + (s[v] == '0')) { dist2[u] = dist2[v] + (s[v] == '0'); q.push(mp(-dist2[u], u)); } } } vector<int> changes; int y = 0; for (int i = 0; i < k; ++i) { y += rd1[p[i]] - 2; int rd2 = dist2[p[i]] + 1; if (rd2 != 1e9) { changes.pb(rd2 - rd1[p[i]] + 1); } } changes.pb(0); sort(all(changes)); vector<int> ans(n, 1e9); { marked.assign(n, false); vector<int> D(n, 1e9); D[st] = 0; q.push(mp(0, st)); ans[st] = 0; while (!q.empty()) { int v = q.top().s; q.pop(); if (marked[v]) { continue; } marked[v] = true; for (auto &u : graph[v]) { ans[u] = min(ans[u], D[v] + 1); if (s[u] == '1') { continue; } if (D[u] > D[v] + 1) { D[u] = D[v] + 1; q.push(mp(-D[u], u)); } } } } int nowk = k * 2 + 1; int x = 0; for (auto &xd : changes) { y += (xd - x) * nowk; x = xd; --nowk; int lb = y - x * nowk; marked.assign(n * 2, false); vector<int> D(n * 2, 1e9); D[st] = lb; q.push(mp(0, st)); while (!q.empty()) { int v_ = q.top().s; q.pop(); if (marked[v_]) { continue; } marked[v_] = true; int v = v_ % n; for (auto u : graph[v]) { int u_ = u; if (v_ >= n || s[u] == '1') { u_ += n; } if (v_ >= n) { ans[u] = min(ans[u], D[v_] + 1); } int td = D[v_] + 1; if (s[u] == '1') { td += nowk; ans[u] = min(ans[u], td); } if (D[u_] > td) { D[u_] = td; q.push(mp(-D[u_], u_)); } } } } for (int i = 0; i < n; ++i) { cout << ans[i] << endl; } } signed main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #else ios::sync_with_stdio(false); cin.tie(0); #endif int t = 1; // cin >> t; while (t--) { solve(); } }