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

#include <cstdio>
//#include <conio.h>
#include <cstring>
#include <queue>
using namespace std;

#define N   11
#define QS  370000

int a[N];//={9,1,7,6,5,4,3,2,8};
int p[N],t[N];//,q[N];
int n,m;
int ans=-1;

int v[N][N];
int deg[N];

int sp;
queue<int> q;
char u[QS];
int lev[QS];


inline int code()
{
    int i,r=0,j;

    for (i=1;i<=n;++i) p[i-1]=i;
    for (i=0;i<n;++i) {
        for (j=0;a[i]!=p[j];++j);
        r = r*(n-i) + j;

        for (j++;j<n-i;++j) p[j-1]=p[j];
    }
    return r;
}

inline void dec(int r)
{
    int i,j,d;
    
    for (i=1;i<=n;++i) p[i-1]=i;

    for (i=1;i<=n;++i) {
        d=r%i;
        t[i]=d;
        r=(r-d)/i;
    }

    for (i=n;i>0;--i) {
        a[n-i]=p[t[i]];
        for (j=t[i]+1; j<i; ++j) p[j-1]=p[j];
    }

}

void print()
{
    for (int i=0;i<n;++i)printf("%d,",a[i]);
    printf("\n");
}

void bfs()
{
    memset(u,0,sizeof(u));
    u[sp]=1;
    q.push(sp);
    lev[sp]=0;

    int i,j,k,c,tmp;

    while (!q.empty()) {
        c=q.front(); q.pop();
        dec(c);

        if (c==0) {
            ans=lev[0];
            return;
        }

        for (i=1;i<=n && a[i-1]!=1;++i);

        //for (i=1;i<=n;++i) {
            for (k=0;k<deg[i];++k) {
                j=v[i][k];

                swap(a[i-1],a[j-1]);

                tmp=code();
                if (!u[tmp]) {
                    u[tmp]=1;
                    q.push(tmp);
                    lev[tmp]=1+lev[c];
                }
                
                swap(a[i-1],a[j-1]);
            }
        //}
    }
    
}


int main()
{
//    clrscr();

    int i,j,x,y;

    FILE *fin=stdin;//fopen("move.in","r"); // !!!
    fscanf(fin,"%d %d",&n,&m);
    for (i=0;i<=n;++i) deg[i]=0;
    for (i=0;i<m;++i) {
        fscanf(fin,"%d %d",&x,&y);
        v[x][deg[x]]=y;
        v[y][deg[y]]=x;
        deg[x]++;
        deg[y]++;
    }
    for (i=0;i<n;++i) {
        fscanf(fin,"%d",&a[i]);
    }
    sp=code();

    //fclose(fin);

    bfs();

    printf("%d\n",ans);

//    getch();
    return 0;
}
