/*
TASK:move
LANG:C++
*/

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>

using namespace std;

#define MAXN 10

#define swap(a,b) ((a)^=(b)^=(a)^=(b))

int g[MAXN][MAXN];
int N, M;
long long start;
long long end;
queue <pair <long long, int> > q;
set <long long> s;
long long ans;

inline long long code(const int * m) {
    ans = 0;
    for (int i = N-1; i >= 0; i--) {
        ans *= MAXN;
        ans += m[i];
    }
    return ans;
}
    
int bfs(void) {
    q.push(make_pair(start, 0));
    s.insert(start);
    
    long long cur;
    long long next;
    int step;
    int c[MAXN];
    int i;
    int plOne;
    
    if (start == end) {
        return 0;
    }
    
    while (!q.empty()) { 
        cur = q.front().first;
        step = q.front().second;
        q.pop();
        for (i = 0; i < N; i++) {
            c[i] = cur%10;
            cur/=10;
            if (c[i] == 1) {
                plOne = i;
            }
        }
        for (int i = 0; i < N; i++) {
            if (g[plOne][i] == 1) {
                swap(c[plOne], c[i]);
                next = code(c);
                if (next == end) {
                    return step + 1;
                }
                if (s.count(next) == 0) {
                    q.push(make_pair(next, step+1));
                    s.insert(next);
                }
                swap(c[plOne], c[i]);
            }
        }
    }
    return -1;
}  

int main() {
    
    //freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
    
    scanf("%d%d", &N, &M);
    
    int a, b;
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &a, &b);
        g[--a][--b] = 1;
        g[b][a] = 1;
    }
    
    int c[MAXN];
    for (int i = 0; i < N; i++) {
        scanf("%d", &c[i]);
    }
    
    start = code(c);
    for (int i = 1; i <= N; i++) {
        c[i-1] = i;
    }
    end = code(c);

    printf("%d\n", bfs());
    
    return 0;
}
