图上的八数码

题目描述

高桥在路边捡到了一个谜题。

它由一个具有 9 个顶点、$M$ 条边的无向图，以及 8 个棋子组成。

图的 9 个顶点分别称为顶点 $1$，顶点 $2$，$\ldots$，顶点 $9$。 对每个 $i = 1, 2, \ldots, M$，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

8 个棋子分别称为棋子 $1$，棋子 $2$，$\ldots$，棋子 $8$。 对每个 $j = 1, 2, \ldots, 8$，棋子 $j$ 位于顶点 $p_j$ 上。

这里保证所有棋子都在互不相同的顶点上。 注意恰好有一个空顶点，上面没有棋子。

高桥可以对谜题执行以下操作任意多次（可以为 0 次）。

选择位于空顶点的某个相邻顶点上的棋子，把它移动到空顶点。

他希望通过反复执行该操作来完成谜题。 当以下条件成立时，认为谜题完成：

对每个 $j = 1, 2, \ldots, 8$，棋子 $j$ 位于顶点 $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

通过以下 5 次操作完成谜题。

把棋子 2 从顶点 9 移动到顶点 1。

把棋子 3 从顶点 2 移动到顶点 9。

把棋子 2 从顶点 1 移动到顶点 2。

把棋子 1 从顶点 3 移动到顶点 1。

把棋子 3 从顶点 9 移动到顶点 3。

另一方面，少于 5 次操作无法完成谜题。因此，应输出 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

数据范围

• 输入均为整数。
• $0 \le M \le 36$
• $1 \le u_i, v_i \le 9$
• 给定的图没有重边或自环。
• $1 \le p_j \le 9$
• $j \neq j' \Rightarrow p_j \neq p_{j'}$