#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pb push_back #define ff first #define ss second #define INF 1000000001LL #define POT (1LL<<23) #define INFL 1000000000000000099LL #define pii pair<ll,ll> #define ppi pair<pii,ll> #define pip pair<ll,pii> #define ppp pair<pii,pii> #define vi vector<ll> #define vii vector<pii> #define vvi vector<vi> #define al(x) x.begin(),x.end() #define rev(x) reverse(al(x)) #define X 18 #define FCTCST 7 template<typename T, typename U> pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) { return {a.first + b.first, a.second + b.second}; } template<typename T, typename U> pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) { return {a.first - b.first, a.second - b.second}; } template<typename T, typename U,typename Z> pair<T, U> operator*(const pair<T, U>& a, const Z& b) { return {a.first*b, a.second*b}; } template<typename T, typename U,typename Z> pair<T, U> operator/(const pair<T, U>& a, const Z& b) { return {a.first/b, a.second/b}; } template<typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os<<"{"<<p.ff<<", "<<p.ss<<"}"; return os; } template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "{"; for (size_t i = 0; i < v.size(); ++i) { if (i) os << ", "; os << v[i]; } os << "}"; return os; } template<ll MOD=998244353> struct mint_t{ ll x; mint_t(ll y=0){x=y%MOD;if(x<0)x+=MOD;} mint_t& operator+=(const mint_t& a){if((x+=a.x)>=MOD)x-=MOD;return *this;} mint_t& operator-=(const mint_t& a){if((x+=MOD-a.x)>=MOD)x-=MOD;return *this;} mint_t operator+(const mint_t& a)const{mint_t res(*this);return res+=a;} mint_t operator-(const mint_t& a)const{mint_t res(*this);return res-=a;} mint_t& operator*=(const mint_t& a){(x*=a.x)%=MOD;return *this;} mint_t operator*(const mint_t& a)const{mint_t res(*this);return res*=a;} mint_t fp(ll y)const{ mint_t a=1,b=x; while(y){ if(y&1)a*=b; b*=b; y/=2; } return a; } mint_t& operator/=(const mint_t& a){(*this)*=a.fp(MOD-2);return *this;} mint_t operator/(const mint_t& a)const{mint_t res(*this);return res/=a;} }; #define mint mint_t<> template<long long MOD> istream& operator>>(istream& in, mint_t<MOD>& a){ ll x; in>>x; a=mint_t<MOD>(x); return in; } template<long long MOD> istream& operator<<(istream& out, mint_t<MOD>& a){ out<<a.x; return out; } mint fct[FCTCST]; mint bnm(ll a,ll b){ if(b>a || a<0)return 0; return fct[a]/fct[b]/fct[a-b]; } ll n,m,k,a,b; vi v; bool bl[50007],bl2[50007]; vi g[50007]; ll dst[50007],dst2[50007],ds[50007]; const ll cns=233; ll ds2[50007][cns+2],mn[50007]; ll ksz[50007],ksz2[100007],rs[50007]; ll ds3[50007][2]; void solve(){ cin>>n>>m>>k; for(ll i=0;i<100007;i++)ksz2[i]=INF; for(ll i=0;i<m;i++){ cin>>a>>b; g[a].pb(b);g[b].pb(a); }ll sm=0; for(ll i=0;i<n;i++){mn[i+1]=INF; char c;cin>>c;bl[i+1]=c-'0';sm+=c-'0'; for(ll j=0;j<=cns;j++)ds2[i+1][j]=INF; } ll st;cin>>st; for(ll i=1;i<k;i++){ cin>>a;v.pb(a); } for(ll i=1;i<=n;i++){ for(ll j:g[i])if(bl[i]&&bl[j])bl2[i]=1; // cout<<bl[i]<<" "<<bl2[i]<<"\n"; } queue<pii>q; for(ll i=1;i<=n;i++){ if(bl[i])q.push({0,i}); } while(q.size()){ pii x=q.front();q.pop(); if(dst[x.ss])continue; dst[x.ss]=x.ff; for(ll i:g[x.ss])q.push({x.ff+1,i}); } deque<pii>pq; for(ll i=1;i<=n;i++){dst2[i]=-1; if(bl2[i])pq.pb({0,i}); } while(pq.size()){ pii x=pq.front();pq.pop_front(); if(dst2[x.ss]!=-1)continue; dst2[x.ss]=x.ff; for(ll i:g[x.ss]){ if(bl[x.ss])pq.push_front({x.ff,i});else pq.pb({x.ff+1,i}); } } vii v2; // for(ll i=1;i<=n;i++){ // cout<<pii{dst[i]-2+(dst2[i]==0),dst2[i]}<<" "; // }cout<<endl; for(ll i : v){ v2.pb({dst[i]-2+(dst2[i]==0),dst2[i]}); } //cout<<v2; bl[st]=0; ll bs=INF; queue<ppi>q1,q2; q1.push({{0,0},st}); while(q1.size() || q2.size()){ if(q1.empty())swap(q1,q2); ppi x=q1.front(); // cout<<x<<"\n"; q1.pop(); if(x.ff.ff<mn[x.ss])mn[x.ss]=x.ff.ff; if(x.ff.ff>=cns+mn[x.ss])continue; if(ds2[x.ss][x.ff.ff-mn[x.ss]]!=INF)continue; ds2[x.ss][x.ff.ff-mn[x.ss]]=x.ff.ss; for(ll i : g[x.ss]){ if(bl[x.ss])q2.push({x.ff+pii{1,0},i}); else q1.push({x.ff+pii{0,1},i}); } } for(pii i:v2){ ksz[1]+=i.ff+2; ksz[2]-=i.ff; if(i.ss!=-1) ksz[i.ss+1-i.ff]--; } ksz2[0]=0; for(ll i=1;i<=sm;i++){ if(i!=1)ksz[i]+=ksz[i-1]; ksz2[i]=ksz2[i-1]+ksz[i]; // cout<<ksz[i]<<" "; } for(ll i=1;i<=n;i++){ // cout<<i<<": "; // for(ll j=0;j<=min(cns,sm);j++)cout<<"{"<<mn[i]+j<<", "<<ds2[i][j]<<"}, ";cout<<"\n"; ll bss=INFL; for(ll j=0;j<=min(cns,sm);j++)bss=min(bss,mn[i]+j+ds2[i][j]+ksz2[mn[i]+j]); rs[i]=bss; } if(k<=cns){ ll aksm=ksz[1]; for(ll i=2;i<=sm;i++){ if(i==2 || ksz[i]!=ksz[i-1]){ ll c=ksz[i]+1; // cout<<i<<" "<<c<<" "; ll c2=aksm-(i-1)*ksz[i];//cout<<c2<<"\n"; for(ll j=1;j<=n;j++)ds3[j][0]=ds3[j][1]=INF; queue<ppi>q1,q2; q1.push({{0,0},st}); while(q1.size() || q2.size()){ if(q1.empty())swap(q1,q2); ppi x=q1.front(); q1.pop(); if(ds3[x.ss][x.ff.ss]!=INF)continue; //cout<<x<<"\n"; ds3[x.ss][x.ff.ss]=x.ff.ff; if(x.ff.ss) rs[x.ss]=min(rs[x.ss],c2+x.ff.ff); for(ll i : g[x.ss]){ if(bl[x.ss])q2.push({{x.ff.ff+c,1},i}); else{ while(q2.size() && ppi{x.ff+pii{1,0},i}>q2.front()){q1.push(q2.front());q2.pop();} q1.push({x.ff+pii{1,0},i}); } } } } aksm+=ksz[i]; } } for(ll i=1;i<=n;i++)cout<<rs[i]<<"\n"; } int main(){ fct[0]=1; for(ll i=1;i<FCTCST;i++)fct[i]=fct[i-1]*i; ll t=1; //cin>>t; for(ll i=1;i<=t;i++){ //cout<<"Case #"<<i<<": "; solve(); } }