← 返回题目列表

AtCoder · abc224_d

G. 8 图表拼图

中文机器翻译题面 查看原题

分数: 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

以下过程通过五次操作完成拼图。

  1. 移动棋子 2 来自顶点 9 到顶点 1.
  2. 移动棋子 3 来自顶点 2 到顶点 9.
  3. 移动棋子 2 来自顶点 1 到顶点 2.
  4. 移动棋子 1 来自顶点 3 到顶点 1.
  5. 移动棋子 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