/*
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 e[1000][2];
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;
    
    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;
            printf("%d ", c[i]);
            cur/=10;
        }printf("\n"); system("pause");
        for (i = 0; i < M; i++) {
            swap(c[e[i][0]], c[e[i][1]]);
            next = code(c);
            if ( next == end ) {
                return step + 1;
            }
            q.push(make_pair(next, step+1));
            s.insert(next);
        }
    }
    return -1;
}  

int main() {
    
    //freopen("in.in", "r", stdin);
    
    scanf("%d%d", &N, &M);
    
    int a, b;
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &a, &b);
        e[i][0] = a;
        e[i][1] = b;
    }
    
    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;
}
