Score : $400$ points

问题描述

高桥在路上发现了一个谜题。这个谜题由一个包含九个顶点和 $M$ 条边的无向图，以及八块拼图组成。

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

八块拼图分别称为拼图1、拼图2、……、拼图8。对于每个 $j = 1, 2, \ldots, 8$，拼图 $j$ 放在顶点 $p_j$ 上。这里保证所有拼图都在不同的顶点上，注意存在恰好一个 空 的顶点没有放置拼图。

高桥可以对谜题进行任意次数（包括零次）的如下操作：

选择一个位于与空顶点相邻的顶点上的拼图，并将其移动到空顶点上。

通过重复执行这个操作，他的目标是 完成 这个谜题。当满足以下条件时，谜题被认为已经完成：

• 对于每个 $j = 1, 2, \ldots, 8$，拼图 $j$ 应放在顶点 $j$ 上。

请确定高桥是否有可能完成此谜题。如果可能，找出完成谜题所需的最少操作次数。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

Takahashi found a puzzle along some road.
It is composed of an undirected graph with nine vertices and $M$ edges, and eight pieces.

The nine vertices of the graph are called Vertex $1$, Vertex $2$, $\ldots$, Vertex $9$. For each $i = 1, 2, \ldots, M$, the $i$-th edge connects Vertex $u_i$ and Vertex $v_i$.
The eight pieces are called Piece $1$, Piece $2$, $\ldots$, Piece $8$. For each $j = 1, 2, \ldots, 8$, Piece $j$ is on Vertex $p_j$.
Here, it is guaranteed that all pieces are on distinct vertices. Note that there is exactly one empty vertex without a piece.

Takahashi can do the following operation on the puzzle any number of times (possibly zero).

Choose a piece on a vertex adjacent to the empty vertex, and move it to the empty vertex.

By repeating this operation, he aims to complete the puzzle. The puzzle is considered complete when the following holds.

• For each $j = 1, 2, \ldots, 8$, Piece $j$ is on Vertex $j$.

Determine whether it is possible for Takahashi to complete the puzzle. If it is possible, find the minimum number of operations needed to do so.

Constraints

• $0 \leq M \leq 36$
• $1 \leq u_i, v_i \leq 9$
• The given graph has no multi-edges or self-loops.
• $1 \leq p_j \leq 9$
• $j \neq j' \Rightarrow p_j \neq p_{j'}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$M$

$u_1$ $v_1$

$u_2$ $v_2$

$\vdots$

$u_M$ $v_M$

$p_1$ $p_2$ $\ldots$ $p_8$

Output

If it is possible for Takahashi to complete the puzzle, find the minimum number of operations needed to do so. Otherwise, print $-1$.

Sample Input 1

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

Sample Output 1

5

The following procedure completes the puzzle in five operations.

1. Move Piece $2$ from Vertex $9$ to Vertex $1$.
2. Move Piece $3$ from Vertex $2$ to Vertex $9$.
3. Move Piece $2$ from Vertex $1$ to Vertex $2$.
4. Move Piece $1$ from Vertex $3$ to Vertex $1$.
5. Move Piece $3$ from Vertex $9$ to Vertex $3$.

On the other hand, it is impossible to complete the puzzle in less than five operations. Thus, we should print $5$.
Note that the given graph may not be connected.

Sample Input 2

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

Sample Output 2

0

The puzzle is already complete from the beginning. Thus, the minimum number of operations needed to complete the puzzle is $0$.

Sample Input 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

Sample Output 3

-1

No sequence of operations can complete the puzzle, so we should print $-1$.

Sample Input 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

Sample Output 4

16

update @ 2024/3/10 09:51:21