/*
TASK: move
LANG: C++
*/
#include <stdio.h>
#include <map>
#include <algorithm>
#define MAXN 362886
using namespace std;

 int a[16][16];
 int n,m;
 int q[MAXN];
 int z[16];
 map<int,int> g;
 int cur,t,tmp;
 int s,e;
 int coef[16];

 int main ()
  {
   int i,j,v,u,pom,nv,k;
   scanf("%d%d",&n,&m);
   coef[n]=1;
   for (i=n-1;i>=0;i--)
    coef[i]=coef[i+1]*10;
   for (i=1;i<=m;i++)
    {
     scanf("%d%d",&v,&u);
     v--;u--;
     a[v][u]=a[u][v]=1;
    }
   cur=t=0;
   for (i=1;i<=n;i++)
    {
     scanf("%d",&z[i]);
     cur=cur*10+z[i]-1;
     t=t*10+i-1;
    }
   e=1;
   g[cur]=1;
   q[1]=cur;
   for (s=1;s<=e;s++)
    {
     pom=q[s];
     nv=g[pom]+1;
     if (pom==t) break;
     for (i=0;i<n;i++)
      if ((pom/coef[i+1])%10==0)
       break;
     for (j=0;j<n;j++)
      if (a[i][j])
       {
        k=(pom/coef[j+1])%10;
        tmp=pom;
        tmp+=k*coef[i+1];
        tmp-=k*coef[j+1];
        if(g.find(tmp)==g.end())
         {
          g[tmp]=nv;
          q[++e]=tmp;
         }
       }
    }
   printf("%d\n",g[t]-1);
   return 0;
  }
  
