问题描述

Takahashi在某条路上发现了一个谜题。
它由一个包含9个顶点和M条边的无向图以及8个碎片组成。

图的九个顶点称为顶点1，顶点2，……，顶点9。对于每个i = 1, 2, ……, M，第i条边连接顶点$u_i$和顶点$v_i$。
八个碎片称为碎片1，碎片2，……，碎片8。对于每个j = 1, 2, ……, 8，碎片j位于顶点$p_j$。
在这里，保证所有碎片都位于不同的顶点上。注意，有且仅有一个 空 顶点没有碎片。

Takahashi可以对这个谜题进行任意次数（可能为零）的以下操作。

选择一个与空顶点相邻的顶点上的碎片，并将其移动到空顶点上。

通过重复这个操作，他的目标是完成这个谜题。当满足以下条件时，谜题被认为是完成的。

• 对于每个j = 1, 2, ……, 8，碎片j位于顶点j上。

确定Takahashi是否有可能完成这个谜题。如果可能，找出完成所需的最小操作次数。

约束条件

• $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'}$
• 输入中的所有值都是整数。

---

输入

输入以以下格式从Standard Input给出：

$M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ $p_1$ $p_2$ $\ldots$ $p_8$

输出

如果Takahashi可以完成这个谜题，请找出完成所需的最小操作次数。否则，输出$\-1$。

---

示例输入1

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

示例输出1

5

以下步骤可以在五个操作内完成这个谜题。

1. 将碎片2从顶点9移动到顶点1。
2. 将碎片3从顶点2移动到顶点9。
3. 将碎片2从顶点1移动到顶点2。
4. 将碎片1从顶点3移动到顶点1。
5. 将碎片3从顶点9移动到顶点3。

另一方面，无法在少于五个操作内完成这个谜题。因此，我们应该输出5。
注意，给定的图可能不是连通的。

---

示例输入2

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

示例输出2

0

谜题从一开始就已经完成了。因此，完成这个谜题所需的最小操作次数为0。

---

示例输入3

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

示例输出3

-1

任何一系列操作都不能完成这个谜题，因此我们应该输出$\-1$。

---

示例输入4

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

示例输出4

16