#include<bits/stdc++.h> // #include<atcoder/modint> // #include<atcoder/convolution> #define pb push_back #define eb emplace_back #define mp make_pair #define F first #define S second #define rs resize #define ft front() #define bk back() #define int long long #define vi vector<int> #define vvi vector<vector<int>> #define pii pair<int, int> #define vpii vector<pair<int, int>> #define vc vector<char> #define vb vector<bool> #define mii map<int,int> #define f0r(i,n) for(int i=0;i<n;i++) #define FOR(i,k,n) for(int i=k;i<n;i++) #define r0f(i,n) for(int i = n-1; i >= 0; i--) #define R0F(i,k,n) for(int i = n-1; i >= k; i--) #define all(v) (v).begin(),(v).end() #define rall(v) (v).rbegin(),(v).rend() #define SUM(v) (accumulate(all(v), 0LL)) #define in(a) int a; cin>>a #define in2(a,b) int a,b; cin>>a>>b #define in3(a,b,c) int a,b,c; cin>>a>>b>>c #define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d #define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];} #define out(a) cout<<a<<'\n' #define out2(a,b) cout<<a<<' '<<b<<'\n' #define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n' #define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n' #define pout(a) cout<<a.first<<' '<<a.second<<'\n' #define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl #define dout(a) cout<<a<<' '<<#a<<endl #define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl #define YN(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';} #define yn(x); if(x){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';} #define p2(x) (1LL << (x)) #define pct(x) (__builtin_popcountll((x))) #define ist(x,y) (((x) >> (y)) & 1) template<class T, class U> bool ckmin(T& a, const U& b) { return (T)b < a ? a = (T)b, 1 : 0; } template<class T, class U> bool ckmax(T& a, const U& b) { return a < (T)b ? a = (T)b, 1 : 0; } const int leg = 1e9 + 7; const int mod = 998244353; using namespace std; // using namespace atcoder; // using mint = modint998244353; // using mint = modint1000000007; const int mxn = 5e4 + 5; int B = 505; int n,m,k; bool stop[mxn]; int bad[mxn], good[mxn], dist1[mxn], dist2[mxn], def[mxn]; vi adj[mxn]; // mint fact[mxn], inv[mxn]; // mint C(int n, int r){return fact[n] * inv[n-r] * inv[r];} // mint snb(int n, int r){return C(n + r, n);} void getdist(){ f0r(i,n)dist1[i]=4e18,dist2[i]=4e18; queue<int>q; f0r(i,n){if(bad[i])dist1[i]=0,q.push(i); if(good[i])dist2[i]=0;} while(!q.empty()){ int node = q.front(); q.pop(); for(auto u : adj[node])if(dist1[u]==4e18){dist1[u]=dist1[node]+1,q.push(u);} } deque<int>qu; f0r(i,n)if(good[i])qu.push_front(i); while(!qu.empty()){ int node = qu.front(); qu.pop_front(); for(auto u : adj[node]){ int w = stop[u] ? 0 : 1; if(dist2[node] + w < dist2[u]){ dist2[u] = dist2[node] + w; if(w==0)qu.push_front(u); else qu.push_back(u); } } } //dist1 bad, dist2 good f0r(i,n)if(stop[i])dist2[i]++; f0r(i,n){if(good[i])dist2[i]=1; if(bad[i])dist1[i]=2;} // f0r(i,n)cout<<dist2[i]<<' '; cout<<'\n'; } signed main(){ ios::sync_with_stdio(false); cin.tie(NULL); //ifstream cin(".in"); //ofstream cout(".out"); // fact[0]=1;FOR(i,1,mxn)fact[i]=fact[i-1]*i;inv[mxn-1]=fact[mxn-1].inv();r0f(i,mxn-1)inv[i]=inv[i+1]*(i+1); cin>>n>>m>>k; f0r(i,m){in2(a,b); a--; b--; adj[a].pb(b); adj[b].pb(a);} string sst; cin>>sst; f0r(i,n)stop[i]=(sst[i]-'0'); vi pos(k); f0r(i,k)cin>>pos[i], pos[i]--; int numstop = 0; f0r(i,n)numstop+=stop[i]; if(numstop==0){ //special case no stops queue<int>q; q.push(pos[0]); vi dist(n,4e18); dist[pos[0]]=0; while(!q.empty()){ int node = q.front(); q.pop(); for(auto u : adj[node])if(dist[u]==4e18)dist[u]=dist[node]+1,q.push(u); } f0r(i,n)cout<<dist[i]<<'\n'; return 0; } f0r(i,n)if(stop[i]){ bool ok = 0; for(auto u : adj[i])if(stop[u])ok=1; if(ok)good[i]=1; else bad[i]=1; } getdist(); vi dif(n+5); int sum = 0, sum0 = 0; FOR(i,1,k){ int g = dist2[pos[i]], b = dist1[pos[i]]; def[i] = min(b, g); sum0+=def[i]; if(g <= b)sum++; else sum+=2; if(b < g && g != 4e18)dif[g - b + 2]--; } int t1 = 2; vector<pair<pii,int>> gw; FOR(i,2,n+5){ if(dif[i] != 0){ gw.pb(mp(mp(t1, i-1), sum)); t1=i; sum += dif[i]; } } gw.pb(mp(mp(t1,n+5), sum)); vi ans(n, 4e18); ans[pos[0]]=0; vvi dp(n, vi(3, 4e18)); dp[pos[0]][0] = 0; queue<pii>q; q.push(mp(pos[0],0)); while(!q.empty()){ auto [x,y] = q.front(); q.pop(); for(auto u : adj[x]){ int x_ = u, y_ = y + stop[u]; if(y_ < 3 && dp[x_][y_] > dp[x][y] + 1){ dp[x_][y_] = dp[x][y] + 1, q.push(mp(x_,y_)); } } } f0r(i,n){ if(stop[i])ckmin(ans[i], dp[i][2] + sum0), ckmin(ans[i], dp[i][1]); else ckmin(ans[i], dp[i][1] + sum0), ckmin(ans[i], dp[i][0]); } // vout(ans); // dout(sum0); if(k <= 200){ sum = sum0; f0r(tt, gw.size()){ int t1 = gw[tt].F.F, t2 = gw[tt].F.S, grad = gw[tt].S; //out3(t1,t2,grad); //lower distance, less stops is better priority_queue<pair<pii,int>>q; q.push(mp(mp(0,0), pos[0])); vpii dist(n, mp(4e18,4e18)); dist[pos[0]]=mp(0,0); while(!q.empty()){ int node = q.top().S; q.pop(); for(auto u : adj[node]){ int w = stop[u] ? (grad+1) : 1; if(dist[u].F > dist[node].F + w || (dist[u].F == dist[node].F + w && dist[u].S > dist[node].S + stop[u])){ dist[u].F = dist[node].F + w; dist[u].S = dist[node].S + stop[u]; q.push(mp(mp(-dist[u].F, -dist[u].S), u)); } } } f0r(i,n)if(stop[i] && i != pos[0])dist[i].S--, dist[i].F-=grad; //f0r(i,n)pout(dist[i]); // dout(sum - (t1-1) * grad); f0r(i,n)if(dist[i].S <= t2 && dist[i].S >= t1)ckmin(ans[i], sum - (t1-1) * grad + dist[i].F); sum += (t2-t1+1)*grad; //vout(ans); } } else{ vvi dp(n, vi(B, 4e18)); vi f(n+5); f[1] = sum0; int cur = sum0; f0r(i,gw.size()){ for(int j = gw[i].F.F; j <= gw[i].F.S; j++){ if(j >= f.size())break; cur += gw[i].S; f[j] = cur; } } vi mn(n, 4e18); mn[pos[0]]=0; deque<int>qu; qu.push_front(pos[0]); while(!qu.empty()){ int node = qu.front(); qu.pop_front(); for(auto u : adj[node]){ int w = stop[u]; if(mn[node] + w < mn[u]){ mn[u] = mn[node] + w; if(w==0)qu.push_front(u); else qu.push_back(u); } } } dp[pos[0]][0] = 0; queue<pii>q; q.push(mp(pos[0],0)); while(!q.empty()){ auto [x,y] = q.front(); q.pop(); y += mn[x]; for(auto u : adj[x]){ int x_ = u, y_ = y + stop[u]; if(y_ < B + mn[x_] && dp[x_][y_-mn[x_]] > dp[x][y-mn[x]] + 1){ dp[x_][y_-mn[x_]] = dp[x][y-mn[x]] + 1, q.push(mp(x_,y_-mn[x_])); } } } // f0r(i,5)cout<<dp[6][i]<<' '; cout<<'\n'; f0r(i,n){ if(stop[i]){ f0r(j,B)if(j-1+mn[i] < f.size())ckmin(ans[i], f[j-1+mn[i]] + dp[i][j]); } else{ f0r(j, B)if(j+mn[i]<f.size())ckmin(ans[i], f[j+mn[i]] + dp[i][j]); } } } f0r(i,n)cout<<ans[i]<<'\n'; }