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$。

输入输出样例 #1

输入 #1

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

输出 #1

5

输入输出样例 #2

输入 #2

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

输出 #2

0

输入输出样例 #3

输入 #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

输入输出样例 #4

输入 #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

说明/提示

限制条件

• $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 翻译