分数: 400 点
问题陈述
高桥在某条路上发现了一个谜题。
它由一个有九个顶点的无向图组成, M 边缘,八块。
图的九个顶点称为Vertex 1,顶点 2, \ldots,顶点 9。对于每个 i = 1, 2, \ldots, M, i第一条边连接顶点 u_i 和顶点 v_i.
这八块称为Piece 1,一块 2, \ldots,一块 8。
对于每个 j = 1, 2, \ldots, 8,一块 j 位于顶点 p_j.
在这里,保证所有碎片都位于不同的顶点上。
请注意,只有一个 空 没有一块的顶点。
Takahashi 可以对拼图执行任意次数的以下操作(可能为零)。
选择与空顶点相邻的顶点上的一个棋子,并将其移动到空顶点。
通过重复此操作,他的目的是 完成 拼图。 当以下条件成立时,拼图被认为完成。
- 对于每个 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.
示例输入 1
5 1 2 1 3 1 9 2 9 3 9 3 9 2 4 5 6 7 8
示例输出 1
5
以下过程通过五次操作完成拼图。
- 移动棋子 2 来自顶点 9 到顶点 1.
- 移动棋子 3 来自顶点 2 到顶点 9.
- 移动棋子 2 来自顶点 1 到顶点 2.
- 移动棋子 1 来自顶点 3 到顶点 1.
- 移动棋子 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