E - Magical Ornament 解説 /

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

配点 : 500 点

問題文

AtCoder 王国には 1, 2, \dots, N の番号がついた N 種類の魔法石が流通しています。
高橋くんは、魔法石を一列に並べて飾りを作ろうとしています。
魔法石には隣り合わせにできる組とできない組があります。 隣り合わせにできる組は (魔法石 A_1, 魔法石 B_1), (魔法石 A_2, 魔法石 B_2), \dots, (魔法石 A_M, 魔法石 B_M) の M 組で、それ以外の組は隣り合わせることができません。(これらの組において、石の順序は不問です。)
魔法石 C_1, C_2, \dots, C_K をそれぞれ 1 個以上含む魔法石の列を作ることができるか判定し、作れる場合はそのような列を作るのに必要な魔法石の個数の最小値を求めてください。

制約

  • 入力は全て整数
  • 1 ≤ N ≤ 10^5
  • 0 ≤ M ≤ 10^5
  • 1 ≤ A_i < B_i ≤ N
  • i ≠ j ならば (A_i, B_i) ≠ (A_j, B_j)
  • 1 ≤ K ≤ 17
  • 1 ≤ C_1 < C_2 < \dots < C_K ≤ N

入力

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

N M
A_1 B_1
A_2 B_2
\hspace{7mm}\vdots
A_M B_M
K
C_1 C_2 \cdots C_K

出力

魔法石 C_1, C_2, \dots, C_K を含む魔法石の列を作るのに必要な魔法石の個数の最小値を出力せよ。
作ることができない場合、代わりに -1 を出力せよ。

入力例 1

4 3
1 4
2 4
3 4
3
1 2 3

出力例 1

5

例えば、魔法石を [1, 4, 2, 4, 3] と並べると、魔法石 1, 2, 3 を含む長さ 5 の列を作ることができます。

入力例 2

4 3
1 4
2 4
1 2
3
1 2 3

出力例 2

-1

入力例 3

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

出力例 3

11

例えば、魔法石を [1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2] と並べると、魔法石 1, 2, 7, 9 を含む長さ 11 の列を作ることができます。

Score : 500 points

Problem Statement

There are N kinds of magical gems, numbered 1, 2, \ldots, N, distributed in the AtCoder Kingdom.
Takahashi is trying to make an ornament by arranging gems in a row.
For some pairs of gems, we can put the two gems next to each other; for other pairs, we cannot. We have M pairs for which the two gems can be adjacent: (Gem A_1, Gem B_1), (Gem A_2, Gem B_2), \ldots, (Gem A_M, Gem B_M). For the other pairs, the two gems cannot be adjacent. (Order does not matter in these pairs.)
Determine whether it is possible to form a sequence of gems that has one or more gems of each of the kinds C_1, C_2, \dots, C_K. If the answer is yes, find the minimum number of stones needed to form such a sequence.

Constraints

  • All values in input are integers.
  • 1 ≤ N ≤ 10^5
  • 0 ≤ M ≤ 10^5
  • 1 ≤ A_i < B_i ≤ N
  • If i ≠ j, (A_i, B_i) ≠ (A_j, B_j).
  • 1 ≤ K ≤ 17
  • 1 ≤ C_1 < C_2 < \dots < C_K ≤ N

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
\hspace{7mm}\vdots
A_M B_M
K
C_1 C_2 \cdots C_K

Output

Print the minimum number of stones needed to form a sequence of gems that has one or more gems of each of the kinds C_1, C_2, \dots, C_K.
If such a sequence cannot be formed, print -1 instead.

Sample Input 1

4 3
1 4
2 4
3 4
3
1 2 3

Sample Output 1

5

For example, by arranging the gems in the order [1, 4, 2, 4, 3], we can form a sequence of length 5 with Gems 1, 2, 3.

Sample Input 2

4 3
1 4
2 4
1 2
3
1 2 3

Sample Output 2

-1

Sample Input 3

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

Sample Output 3

11

For example, by arranging the gems in the order [1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2], we can form a sequence of length 11 with Gems 1, 2, 7, 9.