题目描述

在 AtCoder 王国中有 $N$ 种魔法宝石，编号为 $1, 2, \ldots, N$。
Takahashi 正在尝试通过连成一排的宝石来制作一个装饰品。
对于某些宝石对，我们可以将这两个宝石相邻放置；对于其他宝石对，我们则不能。对于可以相邻放置的宝石对，一共有 $M$ 对：(宝石 $A_1$, 宝石 $B_1$), (宝石 $A_2$, 宝石 $B_2$), $\ldots$, (宝石 $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。

示例输入 1

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

示例输出 1

5

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

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