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

#include <cstdio>
#include <climits>
#include <vector>
#include <algorithm>

const int MAXN = 1 << 4;
const int MAX = 1 << 19;

int N, M;
std::vector <int> vec[MAXN];
int ap;
std::vector <char> all[MAX];

int _cntr = 0;
int bfs (int st) {
	static int d[MAX], q[MAX], p3;
	static int i, c, go_id, cp;
	static unsigned j;
	static std::vector <char> go;
	for (i = 0; i < MAX; ++i) d[i] = INT_MAX;
	d[st] = 0;
	q[p3++] = st;
	for (i = 0; i < p3; ++i) {
		c = q[i];
//		printf ("%d %d\n", c, d[c]);
		if (c == 0) return d[c];
		cp = std::find (all[c].begin (), all[c].end (), 0) - all[c].begin ();
		for (j = 0; j < vec[cp].size (); ++j) {
			go = all[c];
//			printf ("try swap %d %d\n", cp, vec[cp][j]);
			std::swap (go[cp], go[vec[cp][j]]);
//			for (int x = 0; x < N; ++x) printf ("%d ", go[x]); printf ("\n");
			go_id = std::lower_bound (all, all + ap, go) - all;
//			printf ("go_id == %d\n", go_id);
			if (d[go_id] == INT_MAX) {
				d[go_id] = d[c] + 1;
				q[p3++] = go_id;
//				printf ("push!\n");
				++_cntr;
			}
		}
	}

	return -1;
}

int main () {
	scanf ("%d%d", &N, &M);
	int i;
	int a, b;
	for (i = 0; i < M; ++i) {
		scanf ("%d%d", &a, &b);
		--a; --b;
		vec[a].push_back (b);
		vec[b].push_back (a);
	}
	
	std::vector <char> crnt (N);
	for (i = 0; i < N; ++i) {
		scanf ("%d", &a);
		crnt[i] = a - 1;
	}

	std::vector <char> c (N);

	for (i = 0; i < N; ++i) c[i] = i;
	do
		all[ap++] = c;
	while (std::next_permutation (c.begin (), c.end ()));
//	printf ("%d\n", ap);

	int id = std::lower_bound (all, all + ap, crnt) - all;
//	printf ("id == %d\n", id);
	printf ("%d\n", bfs (id));
//	fprintf (stderr, "%d\n", _cntr);
/*
	for (i = 0; i < 10; ++i) {
		for (int j = 0; j < N; ++j)
			printf (" %d", all[i][j]);
		printf ("\n");
	}
*/
	return 0;
}
