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

#include <iostream>
#include <fstream>
#include <vector>
#define MAX 42400000
#define MM 16
using namespace std;

//ifstream in; ofstream out;
int n, m;
char vis[MAX];
int a[MM][MM];
int ma3x[MM][MM];
int octal[MM];
int start[MM]; int strt;
int ans = MAX;
int answer;


int recurse(int cur, int num, int steps)
{
int i, c, j;
int tmp;
int nn;
int cans;
int cc;
int min;

//for (i=0; i<n; i++) out << start[i] << " ";
//out << endl;

vis[num] = steps;
if (steps > 42) return 0;
if (num == answer) return 1;
if (steps >= (int)vis[answer]) return 0;

for (i=0; i<n; i++)
    {
    for (c=1; c<a[i][0]; c++)
        {
        tmp = start[i];
        start[i] = start[a[i][c]];
        start[a[i][c]] = tmp;
        for (j=n-2, nn=0; j>=0; j--) 
            {
            nn += octal[n-j-2]*start[j]; 
            }        
        if  ((int)vis[nn] > steps+1)
            {
            cc = recurse(cur, nn, steps+1);
            }        
        start[a[i][c]] = start[i];
        start[i] = tmp;
        }
    }


return cans;
}


void dowork(void)
{
int i;
int cur;
int num = 0;
int save[MM];

for (i=0; i<MM; i++) save[i] = start[i];

for (i=n-2; i>=0; i--) {num += octal[n-i-2]*start[i];}

for (i=0; i<n; i++)
    {
    for (i=0; i<MM; i++) start[i] = save[i];
    cur = recurse(i, num, 0);
    }

return;
}

void input(void)
{
int i, c;
int x, y;

octal[0] = 1;
for (i=1; i<11; i++) octal[i] = octal[i-1]*9;

cin >> n >> m;

for (i=0; i<MM; i++) for (c=0; c<MM; c++) {a[i][c] = 0; ma3x[i][c] = 0;}
for (i=0; i<MM; i++) a[i][0] = 1;
for (i=0; i<MAX; i++) vis[i] = 120;

for (i=0; i<m; i++)
    {
    cin >> x >> y;
    x--; y--;
    ma3x[x][y] = 1; ma3x[y][x] = 1;
    }
for (i=0; i<n; i++)
    {
    for (c=0; c<n; c++)
        {
        if (ma3x[i][c])
           {
           a[i][a[i][0]] = c; a[i][0]++;
           }
        }
    }
for (i=0; i<n; i++) {cin >> start[i]; start[i]--;}
strt = 0;
for (i=0; i<n-1; i++) {strt*=10; strt+=start[i];}

answer = 0;
for (i=n-2; i>=0; i--) answer += i*octal[(n-i)-2];

return;
}

void output(void)
{

if (n == 0) {cout << 0 << endl; return;}
if (n == 1) {cout << 0 << endl; return;}
if ((int)(vis[answer]) == 120) cout << -1 << endl;
else cout << (int)vis[answer] << endl;

//out << answer << endl << endl;
//for (int i=0; i<42; i++) out << (int)vis[i] << endl;

return;
}

int main(void)
{
int i, c;

//in.open("move.in");
//out.open("move.out");

input();
dowork();
output();

return 0;
}

