D-在图上的8拼图

得分：$400$ 分

问题描述

高桥在某条道路上找到了一个拼图。
它由一个具有九个顶点和 $M$ 条边的无向图以及八个拼图块组成。

图的九个顶点被称为顶点 $1$, 顶点 $2$, $\ldots$, 顶点 $9$。对于每个 $i = 1, 2, \ldots, M$，第 $i$ 条边连接了顶点 $u_i$ 和顶点 $v_i$。
八个拼图块被称为块 $1$, 块 $2$, $\ldots$, 块 $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$
• $j \neq j' \Rightarrow p_j \neq p_{j'}$
• 输入中的所有值均为整数。

输入

输入以以下格式从标准输入给出：

$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

5

以下步骤可以在五次操作内完成拼图。

1. 将块 $2$ 从顶点 $9$ 移动到顶点 $1$。
2. 将块 $3$ 从顶点 $2$ 移动到顶点 $9$。
3. 将块 $2$ 从顶点 $1$ 移动到顶点 $2$。
4. 将块 $1$ 从顶点 $3$ 移动到顶点 $1$。
5. 将块 $3$ 从顶点 $9$ 移动到顶点 $3$。

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

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

0

拼图从一开始就是完整的。 因此，完成拼图所需的最小操作次数为 $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

无论如何操作都无法完成拼图，因此我们应该输出 $-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