102243: [AtCoder]ABC224 D - 8 Puzzle on Graph

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

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

Input

题意翻译

高桥在路上捡到了一个谜题玩具,这个谜题由 $9$ 个顶点 $M$ 条无向边,和 $8$ 个棋子组成。顶点编号为 $1 \sim 9$,第 $i$ 条边连接顶点 $u_i$ 和$v_i$,棋子编号为 $1 \sim 8$。图没有重边和自环。 初始状态下,编号 $j$ 的棋子在编号 $p_j$ 顶点上,每个顶点最多只能有一个棋子。每次移动,可以将一个棋子移动到和它相邻的没有棋子的顶点上。相邻指的是两个顶点之间有一条边直接连接。 如果对 $j=1 \sim 8$,编号 $j$ 的棋子都移动到了编号 $j$ 的顶点上,这个谜题就解开了。 问高桥最少需要几次移动才能解开谜题。如果无法解开谜题,输出 $-1$ 。

Output

得分:$400$分

问题描述

高桥在路上发现了一个谜题。

它由一个具有九个顶点和$M$条边的无向图,以及八个部件组成。

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

这八个部件分别称为部件$1$,部件$2$,$\ldots$,部件$8$。 对于每个$j = 1, 2, \ldots, 8$,部件$j$位于顶点$p_j$上。

在这里,保证所有部件都位于不同的顶点上。 请注意,恰好有一个顶点没有部件。

高桥可以对谜题进行任意次数(包括零次)的以下操作。

选择一个位于空顶点相邻顶点上的部件,并将其移动到空顶点。

通过重复此操作,他旨在完成谜题。 当满足以下条件时,认为谜题完成。

  • 对于每个$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

加入题单

上一题 下一题 算法标签: