#include<bits/stdc++.h>
#define Pair pair<ll,int>
#define ar array
#define ll long long
#define ull unsigned long long 
#define pb push_back

using namespace std ;
const ll LLMAX = 9223372036854775807;
const int INF = 1e9;
int n, m, k;
vector<int> adj[100005];
int dist[18][100005];
int arr[18];

void bfs(int idx){
    dist[idx][arr[idx]] = 0;
    queue<int> q;
    q.push(arr[idx]);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for(int k : adj[cur]){
            if(dist[idx][k]==INF){
                dist[idx][k] = dist[idx][cur]+1;
                q.push(k);
            }
        }
    }
}

int dp[18][1<<18];

int solve(int last, int s){
    if(s==(1<<k)-1)
        return 0;
    
    if(dp[last][s]!=-1)
        return dp[last][s];

    int ans = INF;
    for(int i=0; i<k; i++){
        if((1<<i)&s)
            continue;
        ans = min(ans, solve(i, (1<<i)|s) + dist[last][arr[i]]); 
    }

    return dp[last][s] = ans;
}

int main(){
    memset(dp, -1, sizeof(dp));
    cin>>n>>m;
    for(int i=0; i<m; i++){
        int a, b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }

    cin>>k;
    for(int i=0; i<k; i++){
        cin>>arr[i];
    }

    for(int i=0; i<k; i++){
        for(int j=0; j<=n; j++){
            dist[i][j] = INF;
        } 
        bfs(i);
    }

    for(int i=0; i<k; i++){
        if(dist[i][arr[0]] == INF){
            cout<<-1<<endl;
            return 0;
        }
    }

    /*
    for(int i=0; i<k; i++){
        cout<<"src "<<i<<endl;
        for(int j=1; j<=n; j++)
            cout<<dist[i][j]<<" ";
        cout<<endl;
    }
    */

    int ans = INF;
    for(int i=0; i<k; i++){
        ans = min(ans, 1+solve(i, 1<<i));
    }

    cout<<ans<<endl;
}

#include <bits/stdc++.h>
// clang-format off
using namespace std; using ll = int64_t; using ull = uint64_t; using pll = pair<ll,ll>; const ll INF = 4e18;
void print0() {}
template<typename Head,typename... Tail> void print0(Head head,Tail... tail){cout<<fixed<<setprecision(15)<<head;print0(tail...);}
void print() { print0("\n"); }
template<typename Head,typename... Tail>void print(Head head,Tail... tail){print0(head);if(sizeof...(Tail)>0)print0(" ");print(tail...);}
// clang-format on

char win(char a, char b) {
    if ((a == 'R' && b == 'P') || (a == 'S' && b == 'R') || (a == 'P' && b == 'S')) {
      return b;
    }
    return a;
}
int main() {
    ll n0, k;
    cin >> n0 >> k;
    vector<char> s(n0);
    for (ll i = 0; i < n0; i++) {
        cin >> s[i];
    }
    for (ll depth = k; depth > 0; depth--) {
        ll n = s.size();
        vector<char> nxt;
        nxt.push_back(win(s[0], s[1]));
        for(ll i = 2; (i % n) != 0; i += 2) {
            nxt.push_back(win(s[i % n], s[(i + 1) % n]));
        }
        s = nxt;
    }
    print(s[0]);
}