/*
TASK:move
LANG:C++
*/
#include <stdio.h>
#include <vector>
#include <map>
#define min(a,b) (a < b ? a : b)
#define FOR(i,n) for(int i=0;i<(int)n;i++)

typedef std::map<int,int> mii;

std::vector< std::vector<int> > v;
mii dp;
int a[(1<<4)];
int n,m;

int getConf() {
    int res(0);
    for(int i=n;i>=1;i--) { res *=10; res += a[i-1]; }
    return res;
}
int rec(int cur) {
    if(dp.find(cur) != dp.end()) return dp[cur];
    int ccur = cur;
    int savei(-1);
    FOR(i,n) {
             a[i] = (ccur%10);
             ccur/=10;
             if(a[i] == 1) savei = i;
    }
    int best = 99999999;
    dp[cur] = best;
    int i(savei);
    FOR(j,v[i].size())
    {
        int tmp = a[i];
        a[i] = a[ v[i][j] ];
        a[ v[i][j] ] = tmp;
                
        int cc = getConf();
        if(dp.find(cc) == dp.end() || dp[cc]!=99999999)
           best = min(best, rec(cc) + 1 );
                
        tmp = a[i];
        a[i] = a[ v[i][j] ];
        a[ v[i][j] ] = tmp;
    }
    return dp[cur] = best;
}

int main() {
    scanf("%d %d",&n,&m);
    v.resize(n);
    FOR(i,m) {
             int a,b;
             scanf("%d %d",&a,&b);
             v[a-1].push_back(b-1);
             v[b-1].push_back(a-1);
    }
    int start(0),endConfiguration(0);
    for(int i=n;i>=1;i--){ endConfiguration *= 10; endConfiguration += i; }
    int b[10];
    FOR(i,n) { scanf("%d",&b[i]); }
    for(int i=n;i>=1;i--) { start=start*10 + b[i-1]; }
    dp[endConfiguration] = 0;
    int res = rec(start);
    printf("%d\n",(res==99999999) ? -1 : res);
    return 0;
}
