AT_abc224_d [ABC224D] 8 Puzzle on Graph

高桥君在路边捡到了一个拼图。 这个拼图由 $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$ 上。 请判断高桥君是否能够完成拼图。如果可以，请输出完成所需操作次数的最小值；如果无法完成，请输出 $-1$。

输入以如下格式从标准输入读入： > $M$ > $u_1$ $v_1$ > $u_2$ $v_2$ > $\vdots$ > $u_M$ $v_M$ > $p_1$ $p_2$ $\ldots$ $p_8$

如果高桥君能够完成拼图，输出完成所需操作次数的最小值。 如果无法完成，输出 $-1$。

### 限制条件 - $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'}$ - 所有输入均为整数 ### 样例解释 1 通过如下步骤，可以在 $5$ 次操作内完成拼图： 1. 将棋子 $2$ 从顶点 $9$ 移动到顶点 $1$。 2. 将棋子 $3$ 从顶点 $2$ 移动到顶点 $9$。 3. 将棋子 $2$ 从顶点 $1$ 移动到顶点 $2$。 4. 将棋子 $1$ 从顶点 $3$ 移动到顶点 $1$。 5. 将棋子 $3$ 从顶点 $9$ 移动到顶点 $3$。 无法在少于 $5$ 次操作内完成拼图，因此输出 $5$。 请注意，给定的图不一定是连通的。 ### 样例解释 2 拼图一开始就已经完成，因此完成所需的最小操作次数为 $0$。 ### 样例解释 3 无法通过操作完成拼图，因此输出 $-1$。 由 ChatGPT 4.1 翻译