E - 魔法装饰品

得分：500分

问题描述

AtCoder王国中有$N$种魔法宝石，编号为1, 2, ..., N。
Takahashi想要通过排列这些宝石来制作一个装饰品。
对于某些宝石的组合，我们可以将它们相邻放置；对于其他组合，我们不能将它们相邻放置。对于这$M$对可以相邻放置的宝石：(宝石$A_1$, 宝石$B_1$), (宝石$A_2$, 宝石$B_2$), ..., (宝石$A_M$, 宝石$B_M$)，而其他组合中的宝石不能相邻放置（这些组合中的顺序不重要）。
确定是否可以形成一个宝石序列，其中至少包含种类$C_1, C_2, \dots, C_K$的宝石。如果答案是肯定的，找到形成这样一个序列所需的最小宝石数量。

约束

• 输入中的所有值均为整数。
• $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。

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

5

例如，通过按顺序排列宝石$[1, 4, 2, 4, 3]$，我们可以形成一个长度为$5$，包含宝石$1, 2, 3$的序列。

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]$，我们可以形成一个长度为$11$，包含宝石$1, 2, 7, 9$的序列。