#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int MOD = pow(10,9)+7;
const int MOD2 = 998244353;
const int INF = LLONG_MAX/2;
 
int primes[1000000];
 
void seive(){
    fill(primes, primes + 1000000, 1);
    primes[0] = primes[1] = 0;
    for(int i = 2 ; i*i < 1000000 ; i++){
        if(primes[i]){
            for(int j = i*i ; j < 1000000 ; j += i){
                primes[j] = 0;
            }
        }
    }
    for(int i = 1 ; i < 1000000 ; i++){
        primes[i] += primes[i-1];
    }
}
int factorial(int n){
    if(n==0){
        return 1;
    }
    return (n*(factorial(n-1)))%MOD;
}
bool isPrime(int n){
    if(n <= 1) return false;
    for(int i = 2 ; i*i <= n ; i++){
        if(n % i == 0) return false;
    }
    return true;
}
 
int power(int a, int b){
    if(b == 0) return 1;
    a %= MOD;
    int value = power(a, b / 2);
    if(b % 2 == 0){
        return (value * value) % MOD;
    } else {
        return ((value * value) % MOD * (a % MOD)) % MOD;
    }
}
 
int gcd(int a, int b){
    if(a == 0) return b;
    return gcd(b % a, a);
}
void solve() {
    int n1,m1;
    cin>>n1>>m1;
    vector<int>A[n1+1];
    int value[n1+1];
    for(int i = 0 ; i<m1 ; i++){
        int a,b;
        cin>>a>>b;
        A[a].push_back(b);
        A[b].push_back(a);
    }
    for(int i = 1 ; i<=n1 ; i++){
        cin>>value[i];
    }
    int d;
    cin>>d;
    queue<int>q;
    int visited[n1+1] = {0},visited2[n1+1] = {0};
    int level[n1+1] = {0},level2[n1+1] = {0};
    int five[n1+1] = {0},five2[n1+1] = {0};
    int ways[n1+1] = {0};
    visited[d] = 1;
    if(value[d]==5){
        five[d] = 1;
    }
    q.push(d);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        for(auto node1 : A[node]){
            if(!visited[node1]){
                q.push(node1);
                visited[node1] = 1;
                level[node1] = level[node]+1;
                if(value[node1]==5){
                    five[node1] = 1+five[node];
                }
                else{
                    five[node1] = five[node];
                }
            }
            else{
                if((level[node]+1)==(level[node1])){
                    if(value[node1]==5){
                        five[node1] = max((1+five[node]),five[node1]);
                    }
                    else{
                        five[node1] = max(five[node],five[node1]);
                    }
                }
            }
        }
    }
    visited2[d] = 1;
    ways[d] = 1;
    q.push(d);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        for(auto node1 : A[node]){
            if(!visited2[node1]){
                q.push(node1);
                level2[node1] = level2[node]+1;
                if(value[node1]==5){
                    five2[node1] = 1+five2[node];
                }
                else{
                    five2[node1] = five2[node];
                }
                if(five2[node1] == five[node1]){
                    ways[node1] = ways[node];
                }
                visited2[node1] = 1;
            }
            else{
                if((level2[node]+1)==(level2[node1])){
                    if(value[node1]==5){
                        five2[node1] = max((1+five2[node]),five2[node1]);
                    }
                    else{
                        five2[node1] = max(five2[node],five2[node1]);
                    }
                    if(five2[node1]==five[node1]){
                        ways[node1] = ways[node1] + ways[node];
                    }
                }
            }
        }
    }
    for(int i = 1 ; i<n1+1 ; i++){
        cout<<"No of paths having shortest length from node 1 to node "<<i<<" and maximum no of 5s are : "<<ways[i]<<endl;
    }
}
 
signed main(){
    ios::sync_with_stdio(false); cin.tie(NULL);
    //int t;
    //cin >> t;
    //while(t--){
        solve();
    //}
    return 0;
}