配点 : $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$ を出力せよ。

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

5

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

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

一方、$5$ 回未満の操作でパズルを完成させることはできません。よって、$5$ を出力します。 与えられるグラフは連結とは限らないことに注意してください。

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

0

パズルは初めから完成しています。よって、完成させるために必要な操作回数の最小値は $0$ 回です。

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

-1

操作の繰り返しによってパズルを完成させることができないので、$-1$ を出力します。

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

16