题目描述

高桥在路上看到了一个拼图游戏。

它包含一个有九个点和 $M$ 条边的无向图和八个棋子。

图上的九个点从 $1$ 到 $9$ 编号。对于每个 $i = 1, 2, \ldots, M$，第 $i$ 条边连接点 $u_i$ 和 $v_i$。

八个棋子从 $1$ 到 $8$ 编号。对于每个 $j = 1, 2, \ldots, 8$, 棋子 $j$ 在点 $p_j$ 上。

保证棋子在不同的点上。恰有一个点上没有棋子，称这样的点为空点。  高桥可以做下述操作任意多次。 选择一个在与空点相邻的点上的棋子，把它移动到空点上。

游戏的目标是达成下述局面。 对于每个 $j = 1, 2, \ldots, 8$, 棋子 $j$ 在点 $j$ 上。

判断这个拼图能否完成。若能，求出所需的最小操作次数。 限制

	$0 \leq M \leq 36$

	$1 \leq u_i, v_i \leq 9$

	图上无重边或自环

	$1 \leq p_j \leq 9$

输入格式

$M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

$p_1$ $p_2$ $\ldots$ $p_8$

输出格式

若拼图可能完成，输出所需的最小操作次数。否则输出 -1。

5

1 2

1 3

1 9

2 9

3 9

3 9 2 4 5 6 7 8

	样例二

输入 
12

8 5

9 6

4 5

4 1

2 5

8 9

2 1

3 6

8 7

6 5

7 4

2 3

1 2 3 4 5 6 8 7

输出 
-1
	样例三

输入

12

6 5

5 4

4 1

4 7

8 5

2 1

2 5

6 9

3 6

9 8

8 7

3 2

2 3 4 6 1 9 7 8

输出

16
	样例四

输入

5

1 2

1 3

1 9

2 9

3 9

1 2 3 4 5 6 7 8

输出

0```