题目描述

高桥在路上捡到了一个谜题玩具，这个谜题由 $9$ 个顶点 $M$ 条无向边，和 $8$ 个棋子组成。顶点编号为 $1 \sim 9$，第 $i$ 条边连接顶点 $u_i$ 和$v_i$，棋子编号为 $1 \sim 8$。图没有重边和自环。

初始状态下，编号 $j$ 的棋子在编号 $p_j$ 顶点上，每个顶点最多只能有一个棋子。每次移动，可以将一个棋子移动到和它相邻的没有棋子的顶点上。相邻指的是两个顶点之间有一条边直接连接。

如果对 $j=1 \sim 8$，编号 $j$ 的棋子都移动到了编号 $j$ 的顶点上，这个谜题就解开了。

问高桥最少需要几次移动才能解开谜题。如果无法解开谜题，输出 $-1$ 。

输入格式

第一行输入一个整数 $m$

接下来 $m$ 行每行两个整数 $u,v$

最后一行输入 $8$ 个空格隔开的整数 $p_1,p_2,p_3,\cdots,p_8$。

输出格式

输出最少移动次数，若不可以输出 -1

5
1 2
1 3
1 9
2 9
3 9
3 9 2 4 5 6 7 8

5

5
1 2
1 3
1 9
2 9
3 9
1 2 3 4 5 6 7 8

0

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

提示

• $0\ \leq\ M\ \leq\ 36$
• $1\ \leq\ u_i,\ v_i\ \leq\ 9$
• $1\ \leq\ p_j\ \leq\ 9$
• $j\ \neq\ j'\ \Rightarrow\ p_j\ \neq\ p_{j'}$
• 输入值均为整数。

Sample Explanation 1

下面的程序通过五次操作完成了谜题。

1. 将顶点 9 上的棋子 2 移动到顶点 1 。
2. 将棋子 3 从顶点 2 移至顶点 9 。
3. 将顶点 1 上的棋子 2 移动到顶点 2 。
4. 将顶点 3 上的棋子 1 移动到顶点 1 。
5. 将顶点 9 上的棋子 3 移至顶点 3 。

另一方面，我们不可能在少于五次的操作中完成这道谜题。因此，我们应该打印 5 。

请注意，给出的图形可能并不相连。

Sample Explanation 2

谜题从一开始就已经完成了。因此，完成谜题所需的最少运算次数为 0 。

Sample Explanation 3

任何运算序列都无法完成谜题，因此我们应该打印 −1