/*
TASK:move
LANG:C
*/

#include <stdio.h>
#include <string.h>

char g[9][9], unknown[362880];
short n;
long f=0, l=0, sPos, queue[362880], queueV[362880];

void addQ(long a, long v)
{
  queue[l]=a;
  queueV[l++]=v;
}

long getQ(long *a)
{
  if(f==l)
    return -1;
  *a=queue[f];
  return queueV[f++];
}

void filli(char *a)
{
  static char i;
  for(i=0; i<n; ++i)
    a[i]=i;
}

char *dPerm(char *a, long x)
{
  static char i, j, v[9], av[9];
  for(i=n-2; i>=0; --i)
  {
    av[i]=x%(n-i);
    x/=(n-i);
  }
  filli(v);
  for(i=0; i<n; ++i)
  {
    a[i]=v[av[i]];
    for(j=av[i]; j<n-1; ++j)
      v[j]=v[j+1];
  }
  return a;
}

long ePerm(const char *a)
{
  static char i, j, v[9];
  static long res;
  res=0;
  filli(v);
  for(i=0; i<n; ++i)
  {
    for(j=0; v[j]!=a[i]; ++j);
    res=res*(n-i)+j;
    for(; j<n-1; ++j)
      v[j]=v[j+1];
  }
  return res;
}

long calc(void)
{
  char i, j, k, a[9];
  long currPos=0, currV=0, nPos;
  memset(unknown, 1, 362880*sizeof(char));
  while(currV!=-1)
  {
    if(currPos==sPos)
      return currV;
    dPerm(a, currPos);
    for(j=0; a[j]; ++j);
    for(k=0; k<n; ++k)
      if(g[j][k])
      {
        a[j]=a[k];
        a[k]=0;
        nPos=ePerm(a);
        if(unknown[nPos])
        {
          unknown[nPos]=0;
          addQ(nPos, currV+1);
        }
        a[k]=a[j];
        a[j]=0;
      }
      currV=getQ(&currPos);
    }
  return -1;
}

void input(void)
{
  char t[9];
  short i, m, x, y;
  memset(g, 0, 81*sizeof(char));
  scanf("%hd %hd", &n, &m);
  for(i=0; i<m; ++i)
  {
    scanf("%hd %hd", &x, &y);
    --x;--y;
    g[x][y]=g[y][x]=1;
  }
  for(i=0; i<n; ++i)
  {
    scanf("%hd", &x);
    t[i]=x-1;
  }
  sPos=ePerm(t);
}

int main(void)
{
  long i;
  input();
  printf("%ld\n", calc());
  return 0;
}

