魔法装饰

题目描述

AtCoder 王国流通着 $N$ 种魔法石，编号为 $1, 2, \dots, N$。

高桥君打算把魔法石排成一列制作装饰。

魔法石之间存在可以相邻的组和不能相邻的组。 可以相邻的组为（魔法石 $A_1,$ 魔法石 $B_1$）,（魔法石 $A_2,$ 魔法石 $B_2$）, $\dots$,（魔法石 $A_M,$ 魔法石 $B_M$）这 $M$ 组，除此之外的组不能相邻。（在这些组中，石头的顺序无关。）

请判断能否制作一个分别包含魔法石 $C_1, C_2, \dots, C_K$ 各 $1$ 个以上的魔法石列；如果能制作，求制作这样的列所需魔法石数量的最小值。

输入格式

输入按以下格式从标准输入给出：

$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。

样例

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

5

例如，把魔法石排成 $[1, 4, 2, 4, 3]$，可以制作一个包含魔法石 $1, 2, 3$、长度为 $5$ 的列。

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

-1

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

11

例如，把魔法石排成 $[1, 6, 7, 5, 8, 3, 9, 3, 8, 10, 2]$，可以制作一个包含魔法石 $1, 2, 7, 9$、长度为 $11$ 的列。

数据范围

• 输入均为整数
• $1 \le N \le 10^5$
• $0 \le M \le 10^5$
• $1 \le A_i \lt B_i \le N$
• 若 $i \neq j$，则 $(A_i, B_i) \neq (A_j, B_j)$
• $1 \le K \le 17$
• $1 \le C_1 \lt C_2 \lt \dots \lt C_K \le N$