D - 8 Puzzle on Graph 解説 /

実行時間制限: 4 sec / メモリ制限: 1024 MB

配点 : 400 点

問題文

高橋君は道端であるパズルを拾いました。
このパズルは、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 回でもよい）だけ行うことができます。

空の頂点に隣接する頂点に置かれたコマを 1 つ選び、選んだコマを空の頂点に移動する。

高橋君は上記の操作を繰り返して、このパズルを「完成」させようとしています。 パズルは、下記の状態を満たしたときに完成となります。

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

下記の手順によって、5 回の操作でパズルを完成させることができます。

  1. コマ 2 を頂点 9 から頂点 1 に移動する。
  2. コマ 3 を頂点 2 から頂点 9 に移動する。
  3. コマ 2 を頂点 1 から頂点 2 に移動する。
  4. コマ 1 を頂点 3 から頂点 1 に移動する。
  5. コマ 3 を頂点 9 から頂点 3 に移動する。

一方、5 回未満の操作でパズルを完成させることはできません。よって、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

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