题目描述

高橋君は道端であるパズルを拾いました。
このパズルは、$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$ に置かれている。

高橋君がパズルを完成させることが可能かどうかを判定し、可能な場合はそのために必要な操作回数の最小値を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$ $p_1$ $p_2$ $\ldots$ $p_8$

输出格式

高橋君がパズルを完成させることが可能な場合は、そのために必要な操作回数の最小値を出力せよ。 高橋君がパズルを完成させることが不可能な場合は、$-1$ を出力せよ。

题目大意

高桥在路上捡到了一个谜题玩具，这个谜题由 $9$ 个顶点 $M$ 条无向边，和 $8$ 个棋子组成。顶点编号为 $1 \sim 9$，第 $i$ 条边连接顶点 $u_i$ 和$v_i$，棋子编号为 $1 \sim 8$。图没有重边和自环。

初始状态下，编号 $j$ 的棋子在编号 $p_j$ 顶点上，每个顶点最多只能有一个棋子。每次移动，可以将一个棋子移动到和它相邻的没有棋子的顶点上。相邻指的是两个顶点之间有一条边直接连接。

如果对 $j=1 \sim 8$，编号 $j$ 的棋子都移动到了编号 $j$ 的顶点上，这个谜题就解开了。

问高桥最少需要几次移动才能解开谜题。如果无法解开谜题，输出 $-1$ 。

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

5

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

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

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

提示

制約

• $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'}$
• 入力はすべて整数

Sample Explanation 1

下記の手順によって、$5$ 回の操作でパズルを完成させることができます。 1. コマ $2$ を頂点 $9$ から頂点 $1$ に移動する。 2. コマ $3$ を頂点 $2$ から頂点 $9$ に移動する。 3. コマ $2$ を頂点 $1$ から頂点 $2$ に移動する。 4. コマ $1$ を頂点 $3$ から頂点 $1$ に移動する。 5. コマ $3$ を頂点 $9$ から頂点 $3$ に移動する。 一方、$5$ 回未満の操作でパズルを完成させることはできません。よって、$5$ を出力します。 与えられるグラフは連結とは限らないことに注意してください。

Sample Explanation 2

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

Sample Explanation 3

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