/*
TASK:move
LANG:C++
*/
#include<stdio.h>
#include<vector>
#include<algorithm>

#define maxn 15

using namespace std;

/*
posveshtava se na moqta liubima Ana
*/


void input();
void solve();
void bfs(int v);
void test();

vector <int> decode_perm(int x);
int code_perm(vector <int> v);

int mx[maxn][maxn] = {0}; int top = 0;
int f[maxn];
int p[maxn];
int N, M;
int queue[4000000]; int a1, a2;
int used[4000000] = {0};


int main()
{
input();
solve();
//test();
return 0;
}

void solve()
{
vector <int> v;
for(int i = 0; i < N; i++)
 v.push_back(p[i]);

int c = code_perm(v);
bfs(c);
}

void bfs(int V)
{
int x;
vector <int> v;
int a, b, t, x_new;
int i;

used[V] = 1;
a1 = 0; a2 = 1;
queue[0] = V;

while(a1 < a2)
 {
 x = queue[a1++];
 v = decode_perm(x);

 for(i = 0; i < N; i++) if(v[i] == 1) break;
 a = i;
 for(i = 1; i <= mx[a][0]; i++)
  {
  b = mx[a][i];
  t = v[a]; v[a] = v[b]; v[b] = t;
  x_new = code_perm(v);
  t = v[a]; v[a] = v[b]; v[b] = t;  
  if(used[x_new] == 0)
   {
   used[x_new] = 1 + used[x];
   queue[a2++] = x_new;
   }
  }
  
 }
printf("%d\n", used[0]-1);
}


void input()
{
int a, b;
scanf("%d%d", &N, &M);
for(int i = 0; i < M; i++)
 {
 scanf("%d%d", &a, &b); a--; b--;
 mx[a][++mx[a][0]] = b;
 mx[b][++mx[b][0]] = a;
 }
for(int i = 0; i < N; i++) scanf("%d", &p[i]);
f[1] = 1; f[0] = 1;
for(int i = 2; i <= 11; i++) f[i] = f[i-1]*i;
}


vector <int> decode_perm(int x)
{
int n = N;
int d, j;
int t[maxn];
int T;

for(int i = 0; i <= N; i++) t[i] = 0;
vector <int> ans;

while(n)
 {
 d = x / f[n-1] + 1;
 ans.push_back(d);
 x %= f[n-1];
 n--;
 }

for(int i = 0; i < N; i++)
 {
 T = 0;
 for(j = 1; j <= N && T <= ans[i]; j++)
  {
  if(t[j] == 0)
   { T++; if(T == ans[i]) break; }
  }
 ans[i] = j; t[ans[i]] = 1;
 }
return ans;
}


int code_perm(vector <int> v)
{
int n = N;
int ans = 0;
int d, j;

while(n)
 {
 d = v[N - n] - 1;
 ans += d*f[n-1];
 for(j = N - n; j < N; j++) if(v[j] > d) v[j]--;
 n--;
 }

return ans;
}


/*
void test()
{
int i;
vector <int> v;
vector <int> v1;

N = 4;
for(i = 0; i < N; i++) v.push_back(i+1);
f[1] = 1; f[0] = 1;
for(int i = 2; i <= 11; i++) f[i] = f[i-1]*i;

do
 {
 printf("%d", code_perm(v));
 v1 = decode_perm(code_perm(v));
 for(i = 0; i < N; i++) printf(" %d", v1[i]); printf("\n");
 } while(next_permutation(v.begin(), v.end()));
}
*/


